[Silver I] Z - 1074

문제 링크

성능 요약

메모리: 31256 KB, 시간: 44 ms

분류

분할 정복, 재귀

문제 설명

한수는 크기가 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. x, y를 시작으로 한다
  2. x, y+1을 방문한다.
  3. x+1, y을 방문한다.
  4. x+1, y+1을 방문한다.

따라서 분할 범위를 반씩 줄여나가다가, 크기가 1이 되면 카운트를 하나 증가하고, 위 과정을 반복하는 식으로 코드를 작성하면 된다....고 생각했다.

import sys
input = sys.stdin.readline
n, r, c = map(int, input().split())
size = 2 ** n

cnt = 0
def visit(x, y, s):
    global cnt
    
    if x == r and y == c:
        print(cnt)
        exit()

    if s == 1:
        cnt += 1
        return

    
    div = s // 2
    visit(x, y, div)
    visit(x, (y+div), div)
    visit((x+div), y, div)
    visit((x+div), (y+div), div)

visit(0, 0, size)
print(cnt)

아이디어는 정확했다 라고 생각하는데, $n$의 크기가 커질수록 제한시간 0.5초에는 절대 못들어간다고 판단하였다.
사실 파이썬에서 아래 테스트 케이스를 돌릴때 258ms가 나는것 보고 아차 싶었다.

10 512 512

혹시나 파이썬만의 문제일까 싶어서 c언어로 똑같은 로직으로 다시 작성해 보았다.

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int r = 0;
int c = 0;
int cnt = 0;
void visit (int x, int y, int s){
    int div = 0;
    
    if (x == r && y == c){
        printf("%d", cnt);
        exit(-1);
    }

    if (s == 1){
        cnt += 1;
        return;
    }
    div = s / 2;
    visit(x, y, div);
    visit(x, y+div, div);
    visit(x+div, y, div);
    visit(x+div, y+div, div);
}
int main(void){
    int n = 0;
    int size = 0;
    scanf("%d %d %d", &n, &r, &c);
    size = pow(2, n);
    visit(0, 0, size);
}

역시나였다.

사실 이 문제의 경우 수학적인 규칙을 찾아 탐색을 해야 풀이 할 수 있는 문제이다.
참고한 글은 이 글 이다.

코드

N, r, c = map(int, input().split())

ans = 0

while N != 0:

	N -= 1

	# 1사분면
	if r < 2 ** N and c < 2 ** N:
		ans += ( 2 ** N ) * ( 2 ** N ) * 0

	# 2사분면
	elif r < 2 ** N and c >= 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 1
		c -= ( 2 ** N )

	# 3사분면    
	elif r >= 2 ** N and c < 2 ** N: 
		ans += ( 2 ** N ) * ( 2 ** N ) * 2
		r -= ( 2 ** N )

	# 4사분면    
	else:
		ans += ( 2 ** N ) * ( 2 ** N ) * 3
		r -= ( 2 ** N )
		c -= ( 2 ** N )

print(ans)

---

회고

아이디어와 구현은 빠르게 됐지만, 시간문제에 걸려서 WA를 받은 문제, 로직을 생각하고 시간복잡도를 계산하는 연습이 필요해보인다.
다만 분할정복에 대한 감은 많이 잡혀서 이제 조금 더 어려운 문제를 도전해도 괜찮을 것 같다는 생각을 했다.