[ 백준 - 14606 ] 피자(Small)

https://www.acmicpc.net/problem/14606

14606번: 피자 (Small)

 

주어진 수를 나누다보면 중복된 값이 나오기 때문에 DP 알고리즘 문제이다.

N의 범위가 작게 주어져서 DP 풀이가 아니여도 풀 수 있을거 같은데, 풀이는 메모이제이션으로 풀었다.

---

[ 📌 풀이 ]

• 주어진 수를 최대한 쪼갠다
  • 높이가 1 인 피자탑으로 분리 시키라는 조건이 있었기 때문에 1까지 쪼갠다
• DP 테이블이 비어있다면 값을 채우고, 값이 채워져 있다면 해당 값을 return 한다.
• DP 테이블을 채울 때 주어진 조건은 갑이 느끼는 즐거움과 쪼개진 피자까지 만들 수 있는 즐거움이다
  • 갑이 느끼는 즐거움: a * b(a, b는 쪼개진 피자판의 높이)
  • 쪼개진 피자까지 만들 수 있는 즐거움: 8을 쪼갠다면 4와 4가 나오기 때문에 dp[8] = dp[4] + dp[4] + 갑이 느끼는 즐거움이 된다
• 값을 쪼개는 조건이 명시되어 있지 않아서 2로 나누어 절반으로 나누었고, 홀 수인 경우 b가 더 크도록 만들었다

[ N이 8로 주어졌을 때 ]

---

[ 📌 주의 사항 ]

• 나에게만 해당하지만 처음에 즐거움에 대한 고려를 하지 않아서 이상한 값이 나왔다 (조건 잘 충족할 것)

---

[ 📌 코드 - Python(1) ]

### recursive (top-down)
import sys

N = int(input())
dp = [0] * 11

def sol(n):
  if n <= 1 or dp[n] != 0:
    return dp[n]

  tmp = n // 2
  a, b = tmp, n - tmp

  dp[n] = sol(a) + sol(b) + (a * b)
  return dp[n]

 

[ 📌 코드 - Python(2) ]

### for loop (bottom-up)
import sys

N = int(input())
dp = [0] * 11

for idx in range(N + 1):
  tmp = idx // 2
  a, b = tmp, idx - tmp
  dp[idx] = dp[a] + dp[b] + (a * b)

print(dp[N])

---

[ 📌 결과 - Python  ]

[ Result - Python ]