BOJ 1074 Z
재귀가 아닌 분할정복으로 풀이한 문제입니다.
사분면을 나누는 것까지는 이해를 하였지만, 구현 상 피지컬 이슈로 구글링을 하였습니다. 다른 문제들에 비해 굉장히 여러 방법이 있었고, 그 중 가장 저에게 이해가 잘 되는 코드를 보고 이해 후 풀이하였습니다.
정답 코드
n, r, c = map(int, input().split())
start = 0
while n > 1:
half_size = (2 ** n) // 2
if r < half_size and c < half_size: # 2사분면
pass
elif r < half_size and half_size <= c: # 1사분면
start += half_size ** 2
c -= half_size
elif half_size <= r and c < half_size: # 3사분면
start += half_size ** 2 * 2
r -= half_size
elif half_size <= r and half_size <= c: # 4사분면
start += half_size ** 2 * 3
r -= half_size
c -= half_size
n -= 1
if r == 0 and c == 0:
print(start)
if r == 0 and c == 1:
print(start + 1)
if r == 1 and c == 0:
print(start + 2)
if r == 1 and c == 1:
print(start + 3)풀이과정
N이 3일 경우 다음과 같은 판이 주어집니다.
여기서 사분면으로 나누고 그 안에서 또 사분면으로 나누면 된다는 것을 알 수 있습니다.
시간복잡도를 줄이기 위해서 사분면 중 2 → 1 → 3 → 4사분면 순서대로 탐색을 하는 것이 좋다고 판단했습니다.
half_size 를 통해 n이 3일 경우 (2**n)//2 수식을 통해 절반의 개수를 구합니다. 그러면 4가 나옵니다.
그렇게 입력받은 N, r, c 중 행과 열인 r, c를 봅니다.
3 7 7이 주어졌을 경우 위와 같이 판이 주어지고 7, 7의 좌표에는 63이 주어집니다.
순차적 풀이과정
- 7, 7은 4사분면에 위치하는 값이기 때문에 분할을 시도한다.
half_size <= r and half_size <= c
half_size가 4이기때문에 4, 4는 48이 나온다. 이렇게 사분면을 확인한다.- 이제 시작 좌표를 알아내야하기 때문에 start 좌표를 수식으로 48을 맞춰준다.
- r과 c를 half_size를 빼준다. 그러면 둘다 7 → 3이 될 것이다.
이는 4사분면만 보는 것이기 때문에 아래 이미지와 같이 만드는 것이다.
- 이제 현재 n, r, c는 2 3 3이 주어진다. n이 2인 이유는 사분면을 한번 잘라냈기 때문에 n -= 1을 해준 것이다.
여기서 또 사분면을 나눠보자. - half_size는 수식에 따라 2가 나온다. r, c가 3이다.
half_size <= r and half_size <= c여기서도 이렇게 4사분면에 위치하는 것을 알 수 있다.- 이제 시작 좌표는
start += half_size ** 2 * 3을 통해 60이 될 것이다. - 위와 같이 r과 c를 half_size를 빼준다. 그러면 둘다 3 → 1이 될 것이다.
- 이제 더이상의 사분면 분할은 불가능하기 때문에 while문에서 조건에 의해 탈출한다.
그 다음 r과 c를 추출한다.
if r == 0 and c == 0:
print(start)
if r == 0 and c == 1:
print(start + 1)
if r == 1 and c == 0:
print(start + 2)
if r == 1 and c == 1:
print(start + 3)- (0, 0) 둘다 0인 경우에는 60, (0, 1)이면 61, (1,0)이면 62, (1, 1) 이면 63이기 때문에
규칙에 의해 아래와 같은 코드를 작성하면 된다.
풀이 후기
사실상 참고 블로그가 없었으면 풀지 못하고 넘겼을 것 같습니다.
알고리즘은 너무나도 어렵고.. 아직 풀 때마다 한계를 빠르게 느끼는 것 같아서 아쉽습니다,, 꾸준히 풀어서 성장하기를 바라며!
참고: https://velog.io/@jajubal/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EB%B0%B1%EC%A4%80-1074-Z
