백준 1074

문제 링크

바둑판 꼴의 정사각형 판에서 node가 0,0에서부터 Z자 형식으로 움직인다는 규칙을 가지고 움직인다. 바둑판의 크기(2**N x 2**N)와 점의 위치(r,c)가 주어졌을 때 node가 해당 위치에 도착하는 시간을 구하는 문제이다.

처음 문제를 보다가 바둑판과 점이 움직이는 위치에 대한 규칙을 찾아보기로 했다.
Z자 형식으로 움직이기 때문에 (0,0)을 기준으로 (2,0)에 도착하는 시간은 4가 된다. 비슷하게 (0,0)을 기준으로 (4,0)에 도착하는 시간은 16, 즉 4**2가 된다. 거꾸로 (0,0)을 기준으로 (1,0)에 도착하는 시간은 1, 즉 4**0이 된다.

이를 일반화해보면 시작점을 기준으로 오른쪽으로 움직이는 거리는 가장 큰 사각형을 짜르는 형식을 통해 구할 수 있을 것이다.

마찬가지로 아래 방향으로 가는 것 역시 여기에 2를 곱해주면 나오게 된다.
((0,0)을 기준으로 (0,1)은 2, (0,2)는 2*4, (0,4)는 2*(4**2) ... .)
이를 일반화해보면 다음과 같은 정답을 얻을 수 있다.

N,r,c = map(int,input().split())

result = 0
for i in range(N+1):
    if r & (1<<i):
        result += 2*4**i
    if c & (1<<i):
        result += 4**i

print(result)

해당 코드는 단순히 r,c라는 숫자를 받는 것에, 위에 설명한 것처럼 단위 자체를 bit(2진수 단위)로 구분해서 사각형을 짜르게 되는 것이기 때문에 다음과 같은 결과를 얻을 수 있었다.

bitmasking에 대한 자세한 설명은 여기를 참고해주세요.