https://www.acmicpc.net/problem/1600 원숭이가 격자판의 왼쪽 맨 위에서 오른쪽 맨 아래로 이동하려고 한다. 이동하는 방법은 두 가지가 있다. 일반적인 동서남북 이동과 체스에서의 말의 이동이다. 말의 이동은 최대 K번 까지 할 수 있다. 이 때, 목적지까지 갈 수 없다면 -1를 출력하고 아니면 이동 횟수의 최소값을 출력하는 문제이다. 일반적인 BFS에서의 이동과는 다르게 말의 이동이 추가되어 있다. 그리고 이동할 때마다 말의 이동 가능 횟수가 줄어든다. 현재 위치에서의 남은 말의 이동 가능 횟수가 다르면 다른 상태로 보고 visit 배열을 3차원으로 선언해준다. visit[x][y][k] = 현재위치가 (x,y)이고 남은 말의 이동 횟수가 k일 때 방문했는가? 큐의 크기만큼 매..
http://codeforces.com/contest/931/problem/B 2^k개의 팀이 각각 순서대로 1~2^k로 팀번호가 정해지고 토너먼트를 한다. 이 때 주어진 a,b팀이 몇번째 라운드에서 만나는지 구하는 문제이다. 결승전에서 만나면 "Final!"을 출력한다. 각 팀을 0부터 indexing해서 a,b를 2로 나누면 다음 라운드의 몇번째 팀인지 알 수 있다. 나눌 때마다 라운드가 증가되고 팀이 절반으로 줄어든다. 이 때 a와 b가 같아지는 시점이 두 팀이 만나는 라운드가 된다. 이 때 팀이 하나라면 결승전이다. 123456789101112#include int main(){ int n,a,b,r=0; scanf("%d %d %d",&n,&a,&b); a--,b--; while(a!=b) a/..
http://codeforces.com/contest/931/problem/A 좌표 상에 친구 두 명이 서 있다. 각각 한 좌표씩 이동할 때마다 피로도가 1,2,3 ... 순차적으로 증가한다. 이 때 두 사람의 피로도의 합을 최소로 하면서 만나는 경우에 그 합을 구하는 문제이다. 두 사람의 좌표의 차에서 절반씩 이동하면 된다. 123456789101112#include int main(){ int a,b,d; scanf("%d %d",&a,&b); d=a-b; if(d