Today
Total
01-28 03:55
관리 메뉴

홍우진의 개발 일기장

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

알고리즘/백준

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

홍우진 2025. 1. 14. 23:42
728x90
반응형

문제 링크


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는 너무 어렵다 ㅠㅠ

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

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

 

체감 난이도: ★☆☆

728x90
반응형
Comments