백준 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]
중에서 최소가 되는 비용을 담는다.
소스코드 :
'BOJ' 카테고리의 다른 글
[백준 15990번] 1, 2, 3 더하기 5 (java) (0) | 2021.02.23 |
---|---|
[백준 9095번] 1, 2, 3 더하기 (java) (2) | 2021.02.23 |
[백준 9184번] 신나는 함수 실행 (java) (0) | 2021.02.23 |
[백준 1969번] DNA (java) (0) | 2021.02.20 |
[백준 2841번] 외계인의 기타 연주 (java) (0) | 2021.02.20 |