[백준] 1074번 파이썬

문제: https://www.acmicpc.net/problem/1074
해결 과정

• 문제를 접하고 어떤 방식으로 풀어야 할지 몰라 많이 돌아간 문제다. 난이도가 낮고 비슷한 문제인 2630번 색종이 만들기를 먼저 풀면 어느정도 도움이 된다.
• 2630번 문제를 풀면서 분할정복을 코드를 적용할 수 있었지만 재귀는 이해가 잘 안되어 풀이법을 상세히 올려주신 분의 게시물을 참고했다.

재귀 풀이

import sys
input = sys.stdin.readline

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


def recursion(N, r, c):
    if N == 0:
        return 0

    return 2 * (r % 2) + (c % 2) + 4 * recursion(N - 1, r // 2, c // 2)


print(recursion(N, r, c))

분할 정복 풀이

import sys
input = sys.stdin.readline

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

# 분할 정복 풀이
answer = 0

while N != 0:
    # 4 등분으로 나누자
    N -= 1

    # 1 사분면
    if r < 2 ** N and c < 2 ** N:
        answer += (2 ** N) * (2 ** N) * 0

    # 2 사분면
    if r < 2 ** N and c >= 2 ** N:
        answer += (2 ** N) * (2 ** N) * 1
        c -= (2 ** N)

    # 3 사분면
    if r >= 2 ** N and c < 2 ** N:
        answer += (2 ** N) * (2 ** N) * 2
        r -= (2 ** N)

    # 4 사분면
    if r >= 2 ** N and c >= 2 ** N:
        answer += (2 ** N) * (2 ** N) * 3
        r -= (2 ** N)
        c -= (2 ** N)

print(answer)

참고 사이트: https://ggasoon2.tistory.com/11