[백준] 14606번: 피자 (Small) / 파이썬

문제 링크

---

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

 

풀이 코드

---

sum = 0
for i in range(1,int(input())):
    sum += i
print(sum)

코드 해석

---

쫌 생각해보니

피자탑의 즐거움 최댓값을 구한다고 하면

피자탑을 하나씩 옮기면서 다 더하면 될 것 같았다.

예를 들어보자면

5의 최댓값 = 4*1 + 3*1 + 2*1 + 1*1 = 10 이라는 것을 알 수 있다.

 

다 풀고 나서 난이도에 비해 너무 쉬워서 검색해봤더니

DP로 풀라고 나온 문제였다.

어쩐지 문제가 너무 쉽더라...

 

DP로 푼다면 이렇게 풀 수 있다.

n = int(input())
dp = [0]*(11)
dp[1] = 0
dp[2] = 1
for i in range(3, n+1):
    m = i//2
    dp[i] = m*(i-m) + dp[m] + dp[i-m]
print(dp[n])

 

DP는 너무 어렵다 ㅠㅠ

뭐 풀었으니 됐다고 생각한다...

오히려 메모리도 아끼고... 실행 시간도 아끼고...

 

체감 난이도: ★☆☆☆☆