[백준 16194번] 카드 구매하기 2 (java)

BOJ

lotus lee 2021. 2. 23. 14:06

백준 16194번 : 카드 구매하기 2

16194번: 카드 구매하기 2

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

www.acmicpc.net

다이나믹 프로그래밍으로 풀었다.

dp 1차원 배열을 만들고 dp[N]는 무게 N일 때의 최소 비용을 담는다.

dp[N]는 dp[0] + dp[N],

dp[1] + dp[N-1] : 무게1 일 때의 최소비용 + 무게 N-1 일 때의 최소비용

dp[2] + dp[N-2]

...

dp[N/2] + dp[N/2]

중에서 최소가 되는 비용을 담는다.