3 분 소요

Z

solved_ac[Class3] Z

문제

한수는 크기가 2^N × 2^N인 2차원 배열을 Z모양으로 탐색하려고 한다. 예를 들어, 2×2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.

image

N > 1인 경우, 배열을 크기가 2^(N-1) × 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.

다음 예는 2^2 × 2^2 크기의 배열을 방문한 순서이다.

image

N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.

다음은 N=3일 때의 예이다.

image

입력

첫째 줄에 정수 N, r, c가 주어진다.

출력

r행 c열을 몇 번째로 방문했는지 출력한다.

제한

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

예제 입력 1

2 3 1

예제 출력 1

11

예제 입력 2

3 7 7

예제 출력 2

63

예제 입력 3

1 0 0

예제 출력 3

0

예제 입력 4

4 7 7

예제 출력 4

63

예제 입력 5

10 511 511

예제 출력 5

262143

예제 입력 6

10 512 512

예제 출력 6

786432

문제 해석

문제의 수학적 규칙을 찾고 재귀 함수를 이용하면 쉽게 풀 수 있는 문제이다. 이런 문제는 보통 graph를 이용하여 전부 다 숫자를 집어넣어서 graph의 일정 부분을 빼내는 것 보다 graph를 이용하지 않고 숫자들의 규칙을 찾아서 단순 연산을 통해 풀어내는게 일반적이다. 필자는 처음에 규칙을 찾지 못해서 2차원 배열을 만들어서 재귀를 이용하여 풀려고 했지만 포기하고 규칙을 찾았다.

풀이

  • 예를 들어 7,7을 찾고 싶다고 해보자.
  • x좌표와 y좌표를 2로 나눈 수는 3,3이다. 나머지는 각 1,1이다.
  • 그리고 3,3에서 2로 나눈 수는 1,1이며 나머지는 각 1,1이다.
  • 1,1에서 2로 나눈 수는 0,0이며 나머지는 각 1,1이다.
  • 자 이제 여기서 규칙을 찾아보자.
  • 0,0의 값은 0이다. 1,1은 3이며 3,3은 15, 7,7은 63이다.
  • 여기서 나머지들은 전부 1,1의 쌍을 이룬다.
  • 2로 나누었을때 나머지가 전부 1인 좌표들인데 0, 3, 15, 63이다.
  • 이걸 점화식으로 풀어내면
    • X1 = X0 * 4 + 3 이 된다.
    • 전 좌표에서 4배를 해준 후 3을 더해주면 그 다음 좌표가 나오는 것이다.

  • 그렇게 해서 (7,6)과 (6,7), (6,6)을 보자

  • (7,6)의 값(62) -> 몫 (3,3)의 값(15) 나머지 (1,0) -> 몫 (1,1)의 값(3) 나머지 (1,1) -> 몫 (0,0)의 값(0) 나머지 (1,1)
    • 첫번째는 2로 나누었을때 나머지가 1,0인 것의 규칙을 찾아야한다.
      • 62 -> 15로 내려왔는데 이렇게 되면 15*4 + 2가 된다.
    • 두번째는 2로 나누었을때 나머지가 1,1인 것의 규칙이다.
      • 이건 위에서 찾았듯이 4배를 해준 후 3을 더해주는것이다.
  • (6,7)의 경우를 보면 (6,7) -> (3,3), 나머지(0,1)이다. 값은 61 -> 15이다.
    • 나머지가 (0,1)인 경우는 15*4 + 1이다.
  • (6,6)의 경우는 (6,6) -> (3,3), 나머지(0,0)이다. 값은 60 -> 15이다.
    • 나머지가 (0,0)의 경우는 15*4 + 0이다.

규칙 결론

  • 좌표를 2로 나누었을때
    • 나머지가 (1,1)인 경우
      • X1 = X0 * 4 + 3
    • 나머지가 (1,0)인 경우
      • X1 = X0 * 4 + 2
    • 나머지가 (0,1)인 경우
      • X1 = X0 * 4 + 1
    • 나머지가 (0,0)인 경우
      • X1 = X0 * 4 + 0
  • 이렇게 깔끔하게 떨어진다.
  • 여기서 우리가 graph의 값을 주지 않은채로 정답을 도출해내려면 어떡해야 할까?
  • 0,0의 좌표값이 0인 것은 알고있다. 그렇다면 나누어서 좌표가 0,0이 될때까지 재귀적 호출을 통해 풀어내면 된다.

첫번째 예시

  1. (7,7)
  2. (3,3) 나머지 (1,1)
  3. (1,1) 나머지 (1,1)
  4. (0,0) 나머지 (1,1)
  • 이렇게 재귀적 호출을 하면 4번부터 다시 거슬러 올라가면서 계산을 하게 된다.
  1. (0,0)의 좌표값은 0 나머지는 (1,1)이니깐 0 * 4 + 3 = 3 을 리턴해준다.
  2. return = 3 * 4 + 3 = 15
  3. return = 15 * 4 + 3 = 63
  4. 정답 = 63

두번째 예시

  1. (7,6)
  2. (3,3) 나머지 (1,0)
  3. (1,1) 나머지 (1,1)

  4. (0,0) 나머지 (1,1)

  5. return = 0 * 4 + 3 = 3
  6. return = 3 * 4 + 3 = 15
  7. return = 15 * 4 + 2 = 62
  8. 정답 = 62

  • 여기서 더 간편하게 하고 싶다면??

  • 나머지가 (1,0)일때는 2를 더해주고 (0,1)일때는 1을 더해주고 (1,1)일때는 3을 더해준다. 그렇다면 x좌표의 나머지에 2를 곱하고 y좌표를 더해준것과 같게 된다.
  • 이게 무슨 말이냐면
    • 3 = (1 * 2) + 1 나머지가 (1,1)
    • 2 = (1 * 2) + 0 나머지가 (1,0)
    • 1 = (0 * 2) + 1 나머지가 (0,1)
    • 0 = (0 * 0) + 0 나머지가 (0,0)

슈도 코드

  • 재귀 함수 정의
  • 좌표값(r, c)을 파라미터로 받는다.
    • 만약 좌표가 (0,0)이 되면
      • 더이상 함수를 호출하지 않고 (0,0)의 값인 0을 리턴해준다.
    • 각 좌표를 2로 나눈 몫과 나머지로 정리한다.
    • 2로 나눈 몫을 재귀함수의 좌표로 호출을 하고 그 값의 4배를 해준 후 x좌표의 나머지에 2배, y좌표의 나머지에 1배를 한 것을 더해준다.
import sys

N, r, c = map(int, sys.stdin.readline().split())

def rec(r, c):
    if r == 0 and c == 0:
        return 0
    a = r % 2
    b = c % 2
    r = r // 2
    c = c // 2
    return rec(r, c)*4 + 2*a + b

print(rec(r, c))

결론

이런식으로 그래프들이 전부 다 입력을 받은 상태로 좌표에 해당하는 값을 도출해내는 문제는 무지성으로 그래프에 값들을 전부 넣어놓고 생각할 것이 아닌 적당한 규칙이 있는지부터 먼저 찾아내는것이 중요하다.

댓글남기기

참고