티스토리 뷰
https://www.acmicpc.net/problem/1074
1. 접근 방식
- 방문하는 r행 c열이 위치하는 사분면에만 집중하자.
N = 3, r = 7, c = 7일 때를 예시를 들면 다음과 같다.
7행 7열은 첫 번째 그림에서 제 4사분면에 위치한다. 따라서 나머지 제 1, 2, 3사분면에 있는 임의의 칸을 몇 번째로 방문하는지는 알 필요가 없으며, 7행 7열이 속한 제 4사분면이 48번째부터 방문한다는 사실만 중요하다.
재귀를 통해 제 4사분면으로 들어가면, 다시 중간 그림처럼 배열이 세팅된다. 7행 7열은 이번에도 제 4사분면에 속하므로, 이것이 속한 제 4사분면이 60번째부터 방문한다는 것에 집중한다.
또 다시 재귀를 통해 제 4사분면으로 들어가자. 7행 7열은 이곳에서도 제 4사분면에 위치하므로, 제 4사분면이 63번째부터 방문한다는 것만 알면 된다.
다시 재귀를 통해 제 4사분면으로 들어가면, 배열의 크기가 1x1이다. 이는 재귀의 종료 조건으로, 정답 63을 반환하며 재귀를 끝낸다.
- 그럼 7행 7열이 속한 제 4사분면이 48번째부터 방문한다는 걸 어떻게 알 수 있을까?
제 4사분면 이전에 제 1, 2, 3사분면에 있는 칸을 모두 방문한다. 제 1사분면에 16칸, 제 2사분면에 16칸, 제 3사분면에 16칸이 존재하므로, 제 4사분면의 첫 번째 칸은 48번째로 방문됨을 알 수 있다.
2. 정답 코드
def fill_quadrants(exp, i, j, r, c):
if exp == 0:
return count[0]
half = 2**(exp - 1)
full = half * 2
quadrants = [
[(i, j), (i + half, j + half)],
[(i, j + half), (i + half, j + full)],
[(i + half, j), (i + full, j + half)],
[(i + half, j + half), (i + full, j + full)]
]
for start, end in quadrants:
if start[0] <= r < end[0] and start[1] <= c < end[1]:
return fill_quadrants(exp - 1, start[0], start[1], r, c)
else:
count[0] += half * half
n, r, c = map(int, input().split())
count = [0]
print(fill_quadrants(n, 0, 0, r, c))
추가로 다른 분들의 제출 답안을 불러보던 중 매우 효율적인 코드가 있어서 첨부한다.
https://www.acmicpc.net/source/65332006
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준] 1992번 쿼드트리 파이썬 풀이 (0) | 2024.01.17 |
---|---|
[백준] 7569번 토마토 파이썬 풀이 (0) | 2023.08.24 |
[백준] 1931번 회의실 배정 파이썬 풀이 (0) | 2023.08.19 |
[백준] 9095번 1, 2, 3 더하기 파이썬 풀이 (0) | 2023.08.18 |
[백준] 1541번 잃어버린 괄호 파이썬 풀이 (0) | 2023.08.17 |