[백준 BOJ] 1074 Z
![[백준 BOJ] 1074 Z](/assets/images/baekjoon.png)
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다..
문제로 이동할려면 여기를 클릭하세요.
풀이
- 분할 정복 문제 =>
재귀로 풀자!
예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N = 1
0 1
2 3
N = 2
0 1 4 5
2 3 6 7
8 9 12 13
10 11 14 15
입력
2 3 1
- go(2, 3, 1)
- 2*2 + go(1, 1, 1)
- 2^2*2 + 2*1 + 1 = 8 + 2 + 1 = 7
입력
3 7 7
- go(3, 7, 7)
- 2^4*3 + go(2, 3, 3)
- 2^4*3 + 2^2*3 + go(1, 1, 1)
- 2^4*3 + 2^2*3 + 2*1+1 = 48 + 12 + 3 = 63
코드