백준 파이썬 1074 Z

🚀접근하기

 재귀 문제

예제 입력 2 인 3,7,7을 예로 들었을 때

1,2,3,4분면으로 나눠주고, 3,7,7(63)은 4사분면에 속한다.

다시 3,7,7은 4사분면에 속한다.

다시 3,7,7은 4사분면에 속한다

 

이런식으로 재귀로 풀어주면 된다.

🎉코드

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

sum = 0

while (N > 0):
    N -= 1

    if r < 2**N:  # 1,2 사분면
        if c < 2**N: # 2사분면
            sum += 0
        else:  # 1사분면
            sum += 2**N * 2**N * 1
            c -= 2**N # 다음 사분면에서 더 작은 사분면으로 진행하기 위함
    else: # 3,4 사분면
        if c < 2**N  : #3사분면
            sum += 2**N * 2**N * 2
            r -= 2**N
        else: #4사분면
            sum += 2**N * 2 **N *3
            r -= 2**N
            c -= 2**N

print(sum)

 

1,2,3,4 분면을 나눠주고, n사분면이면 이미 1.2.3사분면의 탐색이 끝난 것이므로 2**N * 2**N * n-1 을 구해 더해주면 된다. (예를들어 4사분면이면 2**N * 2 **N *3)

 

그리고 중간에 생각지 못한 부분이 있어 '틀렸습니다'가 떴었는데,

그 이유가 예를 들어 4*4 에서 2*2로 더 작은 사분면으로 갈 때, 더 작은 사분면에서는 원하는 숫자가 속한 행과 열이 달라지므로 c, r 값을 바꿔줘야 한다.

 

따라서 c -= 2**N, r -= 2**N을 써주었다.

💪다짐

 

# 재귀니까 입력 값에 따라서 생각해보기

# 무작정 다 만든 후에 입력값을 넣어 결과를 도출하려고 하기 보단

# 처음부터 입력 값에 맞추어서 생각해보기

처음에 무작정 2차원 배열을 만드려고 했는데, 재귀이므로 무작정 다 만든 후에 입력값을 넣어 결과를 도출하려고 하기 보단 처음부터 입력 값에 따라서 문제를 해결해보도록 해야겠다.