(Python/🥈1)백준알고리즘 1074번:Z

 

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

 

문제풀이:

import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')


def func(n,r,c):
    if n == 1:
        return 2 * r + c
    half = (2**n)//2
    if r < half and c < half: # 1사분면
        return func(n-1, r, c)
    elif r < half and c >= half:
        return half * half + func(n-1, r, c-half)
    elif r >= half & c < half:
        return 2 * half * half + func(n-1, r-half, c)
    else:
        return 3 * half * half + func(n-1, r-half, c-half)
 
 
n,r,c =map(int,(input().split()))
print(func(n, r, c))

 

재귀를 생각하는 문제이다. 역시 재귀는 아직 어렵다. 내가 푼 방식은

 

결국에 가장 작은 사각형 2x2 일때 0 1 2 3 이런식으로 4개밖에 안남아 그거를 쭉쭉 재귀로 확장하는것이다.

 

예를들어 2,3,1 일때

 

n = 2이고 3열1행 값을 알고싶으면

n = 1일때의 사각형이 이미 2개가 다 채워져있고 3번째 사각형에 2번값을 구해서

 

2개의 사각형 + 3번째사각형에 2번값(2) 를 더해주면 된다.

 

그러면 위 생각대로 하면 2개사각형(8)+ 그다음꺼(2) 라고 생각해서 10 이 되는데 하나 처리해줘야 하는게 있다.

 

0,0 = 1

0,1 = 2

1,0 = 3

1,1 = 4

이렇게 나와야하는데 그냥 r+c 을 하면 2가 나와 10이다. 그래서 해결하려면 2*r + c 로 바꿔줘야 한다.