프로그래밍/알고리즘
[DP]백준 11052 - 붕어빵 판매하기
붕어빵 판매하기 - 링크 다이나믹 프로그래밍을 이용해서 풀어낼 수 있는 문제. dp[n] = n개의 붕어빵을 팔았을 때 얻을 수 있는 최대 이익. X명의 사람에게 붕어빵 [ N ]개를 팔아야 한다. 맨 처음 사람에게 [ i ]개의 붕어빵을 팔았다고 하면 X-1명의 사람들에게는 [ N-i ]개의 붕어빵을 팔아야 한다. (사람의 수 X는 중요하지 않다. 어차피 다 팔린다고 가정을 하고 풀기 때문. 이해하기 쉽도록 X명이 있다고 표현) 점화식으로 풀어보자. dp[N] = max( p[i] + dp[N-i] , dp[N] ) N개를 한번에 다 파는 경우가 가장 비쌀 수도 있기 때문에, max를 이용해서 최대값을 뽑아낸다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17..
2018. 1. 19. 19:52
최근댓글