[백준][python] 1074번: Z

1074번: Z

• 백준(boj) 1074번

문제

한수는 크기가 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

첫 번째 시도 .

N,r,c = map(int,input().split())
value = 2**(N+N)

while N:
  if 2**(N-1) > r and 2**(N-1) > c:
    value //= 4

  if 2**(N-1) > r and 2**(N-1) <= c:
    value //= 4
    value *= 2

  if 2**(N-1) <= r and 2**(N-1) > c:
    value //= 4
    value *= 3

  if 2**(N-1) <= r and 2**(N-1) <= c:
    value //= 4
    value *= 4
  N -= 1

print(value-1)

»intput

10 512 512

»output

1048575

fail

🌝 Thinking

[백준] [python] 2630번: 색종이 만들기 비슷한 분할 정복 문제.

[아이디어 & 틀린 이유 ]

---

두 번째 시도 .

N,r,c = map(int,input().split())
value = 2**(N+N)

while N:
  pie = 2**(N-1)*(2**(N-1))
  if 2**(N-1) > r and 2**(N-1) > c:
    value -= 3 * pie
   
  elif 2**(N-1) > r and 2**(N-1) <= c:
    value -= 2 * pie
    c -= 2**(N-1)

  elif 2**(N-1) <= r and 2**(N-1) > c:
    value -= 1 * pie
    r -= 2**(N-1)

  elif 2**(N-1) <= r and 2**(N-1) <= c:
    r -= 2**(N-1)
    c -= 2**(N-1)
    
  N -= 1

print(value-1)

»intput

10 512 512

»output

786432

success

🌝 Thinking

[아이디어]

1. 우리는 기준을 $2^{N-1}$ 에서 $2^{N-2}$, $2^{N-3}$ . . . $2^0$ 으로 줄여나간다.

   따라서 찾고자하는 행과 열이 기준보다 크다면 큰 값을 기준에서 빼준다.

   기준은 멈춰있고 찾는 값을 조율하는 원리! 이다

2. 1 , 2 와 같이 4등분을 하였다고 생각하고, 선택되어진 사분면에 따라 찾는 값 조율한다.

   3 , 4

또한, N에 값에 따라 4등분되어서 분배되는 규모또한 다르다. 실패한 코드는 변화하는 N의 값 고려하지 않았다.

1. 0 부터 값이 시작되어짐으로 마지막값에 -1을하여 출력한다.

---

💡 깨달은 점.

1. 도형의 분할정복에서 주로 도형을 나누는 행위를 많이 하게된다.

   그 때 나누는 기준이 적절하게 이동할 수 있지만 (위에 문제참고) 이 문제는 찾고자는 값을

   기준에 따라적절하게 변형하고 그에따라 내부의 값도 변동시켜서 푸는 문제였다.