1074번: Z
한수는 크기가 2N × 2N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다. N > 1인 경우, 배열을
www.acmicpc.net
문제
한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.
코드
처음에 푼 코드 => 시간 초과!
n, r, c = map(int, input().split())
cnt = 0
def visit(length, row, col):
global cnt
if row == r and col == c:
print(cnt)
exit()
if length == 1:
cnt += 1
return
visit(length//2, row, col)
visit(length//2, row, col+length//2)
visit(length//2, row+length//2, col)
visit(length//2, row+length//2, col+length//2)
return
visit(2**n, 0, 0)
- 우리가 찾는 위치가 나오면 바로 몇번째로 방문했는지 출력하고 프로그램을 종료하게 해서 시간 초과를 해결해보려 했지만 배열의 크기가 (2 ^ N) * (2 ^ N) (1 ≤ N ≤ 15)이라서 시간 초과가 났다...
정답 풀이
n, r, c = map(int, input().split())
ans = 0
while n != 0:
n -= 1
# 왼쪽 위
if r < 2**n and c < 2**n:
ans += (2**n) * (2**n) * 0
# 오른쪽 위
elif r < 2**n and c >= 2**n:
ans += (2**n) * (2**n) * 1
c -= (2**n)
# 왼쪽 아래
elif r >= 2**n and c < 2**n:
ans += (2**n) * (2**n) * 2
r -= (2**n)
# 오른쪽 아래
else:
ans += (2**n) * (2**n) * 3
r -= (2**n)
c -= (2**n)
print(ans)
이 코드의 시간 복잡도는 O(n)으로 위의 코드와는 비교가 안되게 짧다.
코드도 복잡하지 않다. r, c가 있는 정사각형으로 점점 정사각형 크기를 줄여가며 찾는다고 생각하면 된다.
'문제풀이 > 분할정복' 카테고리의 다른 글
[Python/파이썬] 백준 2448번 별 찍기 - 11 (0) | 2023.05.08 |
---|---|
[Python/파이썬] 백준 2447번 별 찍기 - 10 (0) | 2023.05.07 |
[Python/파이썬] 백준 1992번 쿼드트리 (0) | 2023.03.15 |
[Python/파이썬] 백준 18222번 투에-모스 문자열 (0) | 2023.03.15 |
[Python/파이썬] 백준 17829번 222-풀링 (0) | 2023.03.14 |