[백준] 1074 Z (python 파이썬)

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

1074번: Z

ZZZ

---

아이디어

1. 숫자를 어떻게 찾지

• 처음에는 배열을 만들어보려 했으나 최대길이가 2^15인걸 보고 접었다.
• 분할 탐색같이 생겼지만 혹시 다른 방법이 있을까 봐 고민하다가 그냥 분할 정복으로 풀기로 했다.

2. 규칙을 찾아야 해

• 문제에서 주어진 그림을 보면 4등분 했을 때 느낌이 온다.
• 4등분 했을때 각각의 첫 번째 요소가 일정한 규칙이 있다는 게 보인다.
• 예를 들어 N = 3으로 주어졌을 때 0 16 32 48이다. 이것을 다르게 표현하면 16 * 0, 16 * 1, 16 * 2, 16 * 3
• N으로 표현하자면 (2^(N//2)) * 0, (2^(N//2)) * 1, (2^(N//2)) * 2, (2^(N//2)) * 3
• 이 방식으로 분할 정복 알고리즘을 적용시키면 된다.
• 마지막으로 2*2 배열이 되었을 때 각 위치에 맞게 +0, +1, +2, +3을 해서 출력해주면 된다.

 

---

코드 설명

def dfs(row, col, n, value):
    n = n // 2

    if row < n and col < n:
        if n == 1:
            print(value)
            exit(0)
        dfs(row, col, n, value)

    elif row < n and col >= n:
        if n == 1:
            print(value + 1)
            exit(0)
        dfs(row, col - n, n, value + n ** 2)

    elif row >= n and col < n:
        if n == 1:
            print(value + 2)
            exit(0)
        dfs(row - n, col, n, value + n ** 2 * 2)

    elif row >= n and col >= n:
        if n == 1:
            print(value + 3)
            exit(0)
        dfs(row - n, col - n, n, value + n ** 2 * 3)

dfs(r,c,size,0)

분할 정복 문제를 코드로 보면 바로 이해하기 어렵다. 비슷한 문제를 풀어보는 것이 도움된다.

 

먼저 함수의 인자로 우리가 찾는 위치(r, c)가 주어지고 배열의 길이(2**N)와 0(우리가 구하는 값)을 받아준다.

 

함수를 실행하면 가장먼저 배열 길이를 반으로 자른다. 이후 r, c의 값에 따라 어디 사분면으로 들어갈지 if문을 사용해 체크해준다.

 

이후 다시 함수를 호출해 주면 되는데 여기서 인자로 받는 값을 설명하자면

먼저 r, c는 들어간 사분면에따라 좌표 조정을 해준다. 위치를 항상 상대적으로 생각해야 하기 때문이다.

 

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

위 사진에 12를 보면. 처음 4 by 4 기준으로는 4 사분면에 속해있지만, 들어가서 2 by 2 기준으로 보면 1 사분면에 속해있다.

이러한 이유로 좌표조정을 해준다.

 

다음으로 value값은 위에 설명한 규칙대로 값을 넣어주면 된다.

마지막으로 2 by 2 에서 어느 사분면에 있는지 판단하고 위치에 맞게 값(0, 1, 2, 3)을 더해 출력해주고 exit(0)를 사용해 종료해준다. 

---

전체 코드

import sys
sys.setrecursionlimit(10**3)

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

def dfs(row, col, n, value):
    n = n // 2

    if row < n and col < n:
        if n == 1:
            print(value)
            exit(0)
        dfs(row, col, n, value)

    elif row < n and col >= n:
        if n == 1:
            print(value + 1)
            exit(0)
        dfs(row, col - n, n, value + n ** 2)

    elif row >= n and col < n:
        if n == 1:
            print(value + 2)
            exit(0)
        dfs(row - n, col, n, value + n ** 2 * 2)

    elif row >= n and col >= n:
        if n == 1:
            print(value + 3)
            exit(0)
        dfs(row - n, col - n, n, value + n ** 2 * 3)

dfs(r,c,size,0)

python 3 로 채점해도 잘 된다.