[백준 1606] 침투 계획 세우기

작성일 | In |

문제 링크

https://www.acmicpc.net/problem/1606

풀이

금고의 위치를 나타내는 좌표는 0이상입니다. 즉, 육각형에서 아래 혹은 오른쪽 아래 방향으로만 나아가도 금고에 도달할 수 있습니다.

금고가 나타날 수 있는 좌표만 보면 $(x,y)$는 $(0,0)$에서 $x+y$만큼 떨어져 있는 위치에 있습니다. 그러므로 한쪽 방향으로만 나아가다가 $x+y$가 목표의 위치랑 같아지면 방향을 바꾸어 목표의 위치까지 간다면 많아도 $10^6$번 이동합니다.

오른쪽 아래 방향은 둘러싸는 한 단계가 끝나는 지점이기 때문에 한칸씩 갈 때마다 $6i$씩 번호가 증가합니다. 좌표에서 $x+y$가 목표의 위치랑 같아 방향을 왼쪽 아래로 바꿔서 나아갈 때 번호를 관찰하면 한번은 $6i-1$만큼 줄어들고 두 번째부터는 1씩 증가합니다. 이를 $(x, y)$가 목표의 위치일때까지 반복하면 번호를 찾아낼 수 있습니다. 오른쪽 아래 방향으로 $x+y$번, 왼쪽 아래 방향으로 많아야 $x+y$번 이동하므로 전체 시간복잡도는 $O(x+y)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
#include<cstdio>

long long i = 1, s = 1;
int ex, ey, x, y;

int main(){
    scanf("%d %d",&ex,&ey);
    while(x != ex + ey) s += i*6, x++, i++;
    if(ex == x && ey == y) return !printf("%lld",s);
    while(ex != x && ey != y) s++, x--, y++;
    printf("%lld",s-(i-1)*6);
}