[BOJ] 백준 1074. Z - 분할정복, 재귀

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

풀이

문제를 보면 일단 N>1인 경우에선 사등분으로 나타난다는 것을 알 수 있다.

N = 1 일때 4분면으로 나누면

1, 2, 3, 4

N = 2 일때 4분면으로 나눈 각각의 제트 시작점은?

0, 4, 8, 12 → 각각 4분면 안에서 또 4분면으로 나누기

N = 3 일때 4분면으로 나눈 각각의 제트 시작점은?

1, 16, 32, 48 → 4분면 안에서 4분면 안에서 4분면으로 나누기

x좌표 y좌표는 각 (0~3) 라고 두면?

1사분면의 가로 < 2^(n-1), 세로 < 2^(n-1)

2사분면의 가로 ≥ 2^(n-1), 세로 < 2^(n-1)

3사분면의 가로 < 2^(n-1), 세로 ≥ 2^(n-1)

4사분면의 가로 ≥ 2^(n-1), 세로 ≥ 2^(n-1)

import sys

# 찾고자 하는 숫자, 행, 열
n, r, c = map(int, sys.stdin.readline().split())

visit = 0

while n!= 0:
    n = n-1
    size = 2 ** n
    # 1사분면의 가로 < 2^(n-1), 세로 < 2^(n-1)

    if r < size and c < size :
        visit += 0
    
    # 2사분면의 가로 ≥ 2^(n-1), 세로 < 2^(n-1)
    elif r < size and c >= size :
        visit += size * size #2사분면의 시작점
        c -= size
        
    # 3사분면의 가로 < 2^(n-1), 세로 ≥ 2^(n-1)
    elif r>= size and c<size:
        visit += size * size * 2
        r -= size  
    
    # 4사분면의 가로 ≥ 2^(n-1), 세로 ≥ 2^(n-1)
    else:
        visit += size * size * 3
        r -= size
        c -= size

print(visit)

n이 1일때까지 n을 감소하며 반복해준다!

꽤나 재밌었던 문제였다.. 아주 오랜만에 느껴봄

풀이

문제를 보면 일단 N>1인 경우에선 사등분으로 나타난다는 것을 알 수 있다.

N = 1 일때 4분면으로 나누면

1, 2, 3, 4

N = 2 일때 4분면으로 나눈 각각의 제트 시작점은?

0, 4, 8, 12 → 각각 4분면 안에서 또 4분면으로 나누기

N = 3 일때 4분면으로 나눈 각각의 제트 시작점은?

1, 16, 32, 48 → 4분면 안에서 4분면 안에서 4분면으로 나누기

x좌표 y좌표는 각 (0~3) 라고 두면?

1사분면의 가로 < 2^(n-1), 세로 < 2^(n-1)

2사분면의 가로 ≥ 2^(n-1), 세로 < 2^(n-1)

3사분면의 가로 < 2^(n-1), 세로 ≥ 2^(n-1)

4사분면의 가로 ≥ 2^(n-1), 세로 ≥ 2^(n-1)

import sys

# 찾고자 하는 숫자, 행, 열
n, r, c = map(int, sys.stdin.readline().split())

visit = 0

while n!= 0:
    n = n-1
    size = 2 ** n
    # 1사분면의 가로 < 2^(n-1), 세로 < 2^(n-1)

    if r < size and c < size :
        visit += 0
    
    # 2사분면의 가로 ≥ 2^(n-1), 세로 < 2^(n-1)
    elif r < size and c >= size :
        visit += size * size #2사분면의 시작점
        c -= size
        
    # 3사분면의 가로 < 2^(n-1), 세로 ≥ 2^(n-1)
    elif r>= size and c<size:
        visit += size * size * 2
        r -= size  
    
    # 4사분면의 가로 ≥ 2^(n-1), 세로 ≥ 2^(n-1)
    else:
        visit += size * size * 3
        r -= size
        c -= size

print(visit)

n이 1일때까지 n을 감소하며 반복해준다!

꽤나 재밌었던 문제였다.. 아주 오랜만에 느껴봄