[알고리즘] 백준 1074 Z (파이썬 풀이)

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

1074번: Z

해결코드

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

while N > 1:
    size = (2 ** N) // 2
    if r < size and c < size: # 2사분면
        pass
    elif r < size and c >= size: # 1사분면
        cnt += size ** 2
        c -= size
    elif r >= size and c < size: # 3사분면
        cnt += size ** 2 * 2
        r -= size
    elif r >= size and c >= size: # 4사분면
        cnt += size ** 2 * 3
        r -= size
        c -= size
    N -= 1

if r == 0 and c == 0:
    print(cnt)
if r == 0 and c == 1:
    print(cnt + 1)
if r == 1 and c == 0:
    print(cnt + 2)
if r == 1 and c == 1:
    print(cnt + 3)

문제풀이

이전 문제와 비슷한 맥락일줄 알았으나, 약간 다르다.

찾아야 하는 좌표가 주어졌을 때, 그 좌표가 어느 사분면에 있는지 계속해서 확인해주어야 한다.

탐색순서가 Z모양 즉, 2-1-3-4 사분면 순이므로

좌표가 2사분면일때는 좌표값을 수정할 필요 없고,

1,3,4 사분면일때는 2사분면에 맞게 좌표를 수정해주어야 한다.

 

코드를 보자

 

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

N값과 찾는 좌표값r,c를 입력받고 탐색한 경로의 수를 저장하는 cnt를 선언한다.

참고로 r이 세로방향이고 , c가 가로방향이다.

 

while N > 1:
    size = (2 ** N) // 2

N이 1보다 크다면 while문을 계속해서 실행한다.

size라는 변수를 선언하고 2**N을 2로 나눠준 값을 저장한다.

(한 사분면의 최대 길이를 저장하는 것)

    if r < size and c < size: # 2사분면
        pass

만약 r과 c 모두 size보다 작다면 2사분면이다. (좌표값 수정할 필요 없음)
    elif r < size and c >= size: # 1사분면
        cnt += size ** 2
        c -= size

r이 size보다 작고 c가 size보다 크거나 같으면 1사분면이다.

(1사분면으로 오기위해서 2사분면을 거쳐야 하므로 size**2를 cnt에 더해준다)

좌표값은 c만 수정해주면 됨

    elif r >= size and c < size: # 3사분면
        cnt += size ** 2 * 2
        r -= size

r이 size보다 크거나 같고 c가 size보다 작다면 3사분면이다.

(3사분면으로 오기위해서 2,1사분면 거치므로 size**2를 cnt에 두 번 더해준다)

좌표값은 r만 수정해주면 됨

    elif r >= size and c >= size: # 4사분면
        cnt += size ** 2 * 3
        r -= size
        c -= size

r과 c 모두 size보다 크다면 4사분면이다.

(4사분면으로 오기 위해서 2,1,3사분면 거치므로 size**2를 cnt에 세 번 더해준다)

좌표값 r과c 모두 수정해주어야 함

    N -= 1

N이 1이 될 때까지 계속해서 1씩 빼주면서 반복한다.

 

if r == 0 and c == 0:
    print(cnt)
if r == 0 and c == 1:
    print(cnt + 1)
if r == 1 and c == 0:
    print(cnt + 2)
if r == 1 and c == 1:
    print(cnt + 3)

 

반복문을 탈출했을 떄 N은 1이고 size는 2일 것이다.(즉 그냥 2*2칸이 하나 남았다는 소리)

그 때 좌표값은 이럴 것이다( 못생긴 그림 양해)

2-1-3-4 사분면 순으로 탐색인걸 기억하며

만약 좌표가 (0,0)이면 cnt값을 그대로 출력

(0,1)이라면 cnt값+1을 출력

(1,0)이라면 cnt값+2를 출력