[solved.ac 실버1] 1074_Z

제한 사항

문제

한수는 크기가 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열을 몇 번째로 방문했는지 출력한다.

제한

• 1 ≤ N ≤ 15
• 0 ≤ r, c < 2N

예제

 

---

나의 풀이

재귀를 사용해서 풀어도 되지만 나는 그냥 반복문을 사용했다.

주어진 그림을 보면 (왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래) 4개로 쪼갤 수 있다.

쪼개진 각각의 부분에서 또 다시 4개로 쪼갤 수 있다.

몇 번을 쪼갤 수 있는지 살펴보면 n번 가능하다. (사용자에게 입력 받은 n)

예를 들어 사용자가 n에 3을 입력했을 때

1. 한 변이 8인 정사각형 하나 -> 한 변이 4인 정사각형 4개
2. 한 변이 4인 정사각형 하나 -> 한 변이 2인 정사각형 4개
3. 한 변이 2인 정사각형 하나 -> 한 변이 1인 정사각형 4개

그래서 4개로 쪼개서 각각을 처리하는 방법을 생각하면 된다.

나는 행의 중간 값과 r을 비교해 위쪽에 속했는지, 아래쪽에 속했는지 판별했고, 열의 중간 값과 c를 비교해 왼쪽에 속했는지, 오른쪽에 속했는지 판별했다. 그리고 사각형에서 시작 숫자와 사각형에 들어갈 수 있는 숫자의 개수를 고려했다.

코드는 다음과 같다.

n, r, c = map(int, input().split())
start = 0 # 사각형의 시작 숫자
for i in range(n-1, -1, -1):
    nums = (2**(i+1))**2 # 사각형의 면적 (1x1 사각형의 개수)
    rc, cc = 2**i, 2**i # rc: 행의 중간, cc: 열의 중간
    if r >= rc:
    # 아래쪽
        start += nums//2 
        r -= rc
    if c >= cc:
    # 오른쪽
        start += nums//4
        c -= cc
print(start)

만약 r, c 위치가 4개로 나눈 사각형 중 아래에 있는 사각형에 속한다면 start에 사각형 면적의 절반만큼 더하고, 오른쪽에 있는 사각형에 속한다면 start에 사각형 면적의 1/4만큼을 더한다.

그리고, r과 c도 재조정해준다.

정해진 횟수만큼 반복문을 돌면 start가 우리가 찾던 답이 된다.

 

N이 최대 15까지 입력될 수 있는데 N이 15일 때 가장 큰 사각형의 한 변 길이는 32,768이 되고, 면적은 1,073,741,824이 된다.

일일히 트래킹한다고 했으면 반복문 한 번 도는데 0.001초가 걸린다고 가정했을 때 10,737,41.824초( =약 12일)가 소요된다.

하지만 위 풀이는 단 15번의 반복문만 돌면 된다. 이게 알고리즘의 힘이다.

채점 결과