홍우진의 개발 일기장
[백준] 14606번: 피자 (Small) / 파이썬 본문
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
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준] 1244번: 스위치 켜고 끄기 / 파이썬 (0) | 2025.01.16 |
---|---|
[백준] 1652번: 누울 자리를 찾아라 / 파이썬 (0) | 2025.01.15 |
[백준] 14501번: 퇴사 / 파이썬 (0) | 2025.01.13 |
[백준] 15720번: 카우버거 / 파이썬 (0) | 2025.01.12 |
[백준] 9461번: 파도반 수열 / 파이썬 (0) | 2025.01.11 |
Comments