문제
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.
만약, N > 1이 라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 크기가 2N-1 × 2N-1로 4등분 한 후에 재귀적으로 순서대로 방문한다.
다음 예는 22 × 22 크기의 배열을 방문한 순서이다.
N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.
다음은 N=3일 때의 예이다.
입력
- 첫째 줄에 정수 N, r, c가 주어진다.
출력
- r행 c열을 몇 번째로 방문했는지 출력한다.
풀이
완전탐색
- 처음에는 시간 초과가 날지도 모르지만 재귀로 4분할을 이어가는 함수를 짜고
r과c를 입력하면 해당값을 바로 가져오게 했다.
- 결과는 당연히 시간초과시간 초과
from sys import stdin, setrecursionlimit input = stdin.readline setrecursionlimit(10000) def Z(a, n, x, y, c): if n == 1: a[x][y], a[x][y+1], a[x+1][y], a[x+1][y+1] = c, c+1, c+2, c+3 else: Z(a, n-1, x, y, c) Z(a, n-1, x, y+2**(n-1), c+2**(2*n-2)) Z(a, n-1, x+2**(n-1), y, c+2*2**(2*n-2)) Z(a, n-1, x+2**(n-1), y+2**(n-1), c+3*2**(2*n-2)) if __name__ == "__main__": N, r, c = map(int, input().split()) array = [[0 for _ in range(2 ** N)] for _ in range(2 ** N)] Z(array, N, 0, 0, 0) print(array[r][c])
분할정복
- 잘 몰랐는데 이렇게 큰 문제를 작게 만들어서 푸는 방식을 '분할 정복'이라고 한다.
- 완전 탐색으로 짰던 코드에서 1, 2, 3, 4 사분면 중 어느 사분면에 있는지 확인하는 조건문 몇개만 붙여주면 완전히 다 돌지 않고 원하는 부분으로만 찾아가는 코드가 완성된다.
답
from sys import stdin, setrecursionlimit input = stdin.readline setrecursionlimit(10000) def z(n, x, y, cnt): if n == 1: if x == r and y == c: return cnt elif x == r and y + 1 == c: return cnt + 1 elif x + 1 == r and y == c: return cnt + 2 else: return cnt + 3 else: if x + 2 ** (n - 1) > r: if y + 2 ** (n - 1) > c: return z(n - 1, x, y, cnt) else: return z(n - 1, x, y + 2 ** (n - 1), cnt + 2 ** (2 * n - 2)) else: if y + 2 ** (n - 1) > c: return z(n - 1, x + 2 ** (n - 1), y, cnt + 2 * 2 ** (2 * n - 2)) else: return z(n - 1, x + 2 ** (n - 1), y + 2 ** (n - 1), cnt + 3 * 2 ** (2 * n - 2)) if __name__ == "__main__": N, r, c = map(int, input().split()) res = z(N, 0, 0, 0) print(res)
최적화?
- 풀이를 작성하며 코드를 보다 굳이
n==1이라는 조건 때문에 코드가 더 길어진 것 같다는 생각이 들어 조건을n==0으로 수정하고 해당 값을 바로 반환하게 만들었다.
- 웃기게도 코드 길이는 짧아졌지만 재귀가 한번 더 들어가게 돼서 그런지 시간은 아주 조금 더 늘었다ㅋㅋ.
답
from sys import stdin, setrecursionlimit input = stdin.readline setrecursionlimit(10000) def Z(n, x, y, cnt): if n == 0: return cnt else: if x+2**(n-1) > r: if y+2**(n-1) > c: return Z(n-1, x, y, cnt) else: return Z(n-1, x, y+2**(n-1), cnt+2**(2*n-2)) else: if y+2**(n-1) > c: return Z(n-1, x+ 2**(n-1), y, cnt+2*2**(2*n-2)) else: return Z(n-1, x+2**(n-1), y+2**(n-1), cnt+ 3*2**(2*n-2)) if __name__ == "__main__": N, r, c = map(int, input().split()) res = Z(N, 0, 0, 0) print(res)
Uploaded by Notion2Tistory v1.1.0