[Baekjoon/🥈SilverⅠ] 1074: Z

🙋‍♀️ Z

문제에 대한 자세한 설명은 위 페이지를 참고!!

🙋‍♀️ 입력

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

🙋‍♀️ 출력

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

🙋‍♀️ 제한

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

👩‍💻 Algoritm: Dvide and Conquer(1)

사실 필자가 작성한 알고리즘이 완벽한 분할 정복에 해당되지는 않는다! 하지만 반복되는 구조를 파악해 단계별로 동일한 작업을 진행하여 최종 답을 구했다는 점에서 분할정복을 적용했다고 볼 수 있다.

그렇다면 바로 알고리즘부터 확인한 후, 한 줄씩 분석해보자!

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

answer = 0

while n > 0:
  answer += (r//2**(n-1))*(2**(n-1)*2**(n-1)*2) # ...1
  answer += (c//2**(n-1))*2**(n-1)*2**(n-1) # ...2

  r -= (r//2**(n-1))*2**(n-1) # ...3
  c -= (c//2**(n-1))*2**(n-1) # ...4
  
  n -= 1
print(answer)

식만 보면 그 원리를 파악하기 힘들 것이다! 다음의 그림과 함께 살펴보자! 아래 그림의 상황은 n=3/r=4/c=5인 경우이다.

• r > 변의 길이 절반(위에서는 4)
  • 절반 크기의 정사각형(4*4) 2개가 이미 존재한다.
• c > 변의 길이 절반(위에서는 4)
  • 절반 크기의 정사각형(4*4) 1개가 이미 존재한다.
• 이미 존재하는 사각형의 개수를 answer에 더해줬으므로 r, c의 값을 갱신해야 한다.
  • r > 4일 경우, 4를 빼준다. r <= 4일 경우, 아무 값도 빼지 않는다.
  • c > 4일 경우, 4를 빼준다. c <= 4일 경우, 아무 값도 빼지 않는다.

n의 값을 하나씩 줄여가며 값을 구하면 다음과 같은 식으로 전개가 된다.

👩‍💻 Algoritm: Dvide and Conquer(2)

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

answer = 0

while n > 0:
  if r < 2**(n-1) and c < 2**(n-1): #1사분면
    answer += 2**(n-1) * 2**(n-1) * 0
  elif r < 2**(n-1) and c >= 2**(n-1): #2사분면
    answer += 2**(n-1) * 2**(n-1) * 1
    c -= 2**(n-1)
  elif r >= 2**(n-1) and c < 2**(n-1):#3사분면
    answer += 2**(n-1) * 2**(n-1) * 2
    r -= 2**(n-1)
  elif r >= 2**(n-1) and c >= 2**(n-1):#4사분면
    answer += 2**(n-1) * 2**(n-1) * 3
    r -= 2**(n-1)
    c -= 2**(n-1)

  n -= 1

print(answer)

해당 알고리즘도 아래 그림을 보면 이해하기 쉬울 것이다!

다음으로는 재귀를 이용한 풀이이다!

👩‍💻 Algoritm: 재귀

🙄 재귀를 이용해 풀이하기 위해서는 규칙성을 찾아야 한다.

아래 그림을 확인해보자!!

위 그림에서 우리는 다음의 규칙을 확인할 수 있다!

x, y 값이 2배가 되면 그 값은 4배가 된다.

• (2,0) = 8 -> (4,0) = 32
• (3,0) = 10 -> (6,0) = 40

따라서 이를 통해 다음의 알고리즘을 작성할 수 있다.

def getAnswer(N, r, c):
  if N == 0:
    return 0
  return 2*(r%2)+(c%2) + 4 * getAnswer(N-1, r//2, c//2)

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

print(getAnswer(n, r, c))

🙄 여기서 2*(r%2)+(c%2)가 무슨 역할인지 궁금할 것이다!!

• 그렇다! 항상 x, y의 값이 정확히 2배가 되는 것은 아니다! 따라서 그 오차를 해결해주는 역할이 위의 식이 된다.

📝 참고 자료

• https://www.acmicpc.net/problem/1074
• https://ggasoon2.tistory.com/11