[BOJ] 1074 - Z

사용 언어: Python3

문제

백준 1074

코드

내 풀이

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

global ans
ans = 0

# length: 보드판 한 변의 길이
# x: 세로 y: 가로
def dfs(length, x, y):
  global ans
  if length == 1:
    return ans
  
  # 분할
  length //= 2
  size = length**2 # 한 사분면의 넓이

  # 찾고자 하는 (x, y) 좌표의 위치
  # 1사분면
  if x < length and y < length:
    ans += size * 0
    return dfs(length, x, y)
  # 2사분면
  elif x < length and y >= length:
    ans += size * 1
    return dfs(length, x, y-length)
  # 3사분면
  elif x >= length and y < length:
    ans += size * 2
    return dfs(length, x-length, y)
  # 4사분면
  elif x >= length and y >= length:
    ans += size * 3
    return dfs(length, x-length, y-length)

print(dfs(2**N, r, c))

• 분할 정복 방법
  • DP와 반대로 Top-Down 방식이다.
  • 따라서 전체부터 시작하여 작은 부분으로 내려간다.
• 전역변수를 사용했다. (전역변수를 사용하지 않고도 풀 수 있을 것 같다.)

다른 풀이

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

# x: 세로축, y: 가로축
def dfs(length, x, y):
  if length == 1:
    return 0
  
  # 분할
  length //= 2

  # 1,2,3,4 사분면 중 어디인지 찾기
  for i in range(2):
    for j in range(2):
      if x < length*(i+1) and y < length*(j+1): # ✅
        size = length**2 # 한 사분면의 넓이
        # 이미 지나온 사분면 넓이 + dfs()
        return (i*2+j)*size + dfs(length, x-length*i, y-length*j) # ✅

      # (i, j)   :   (0,0), (0,1), (1,0), (1,1)
      # 지나온 사분면 수 : 0      1      2      3
      # 표현법    :    i*2+j

# output
print(dfs(2**N, r, c))

• 재귀를 이용한 방법
• 2중 for문을 통해 (x,y)가 1,2,3,4분면 중 어디에 위치하는지 확인할 수 있다.
  
• i*2+j로 이미 지나온 사분면의 수를 나타낼 수 있다.
  • ex) (x,y)가 4사분면에 위치해있다고 가정하자.
    4사분면일 때 (i,j)는 (1,1)
i*2+j = 1*2+1 = 3
    -> 총 3개의 사분면은 이미 지나온 것이다. (1,2,3사분면)

---

💛 개인 공부 기록용 블로그입니다. 👻

맨 위로 이동하기