백준 16194 / 카드 구매하기 2
문제
풀이
설명
카드 N개를 구매해야한다.
카드팩은 총 N가지 종류가 존재한다.
i번째 카드팩은 i개의 카드를 담고있고, 가격은 P[i]원 이다.
카드 N개를 구매하는 비용의 최대값을 구하는 문제
D[i] = 카드i개 구매하는 최대 비용
카드 i개를 구매하는 방법은?
카드 1개가 들어있는 카드팩을 구매하고, 카드 i-1개를 구매
• P[1] + D[i-1]
카드 2개가 들어있는 카드팩을 구매하고, 카드 i-2개를 구매
• P[2] + D[i-2]
…
카드 i-1개가 들어있는 카드팩을 구매하고, 카드 1개를 구매
• P[i-1] + D[1]
카드 i개가 들어있는 카드팩을 구매하고, 카드 0개를 구매
• P[i] + D[0]
D[N] = max(D[n-i]+p[i])
1<=i<=N
코드
import java.util.Scanner;
public class Num16194 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] a = new int[n+1];
for (int i=1; i<=n; i++) {
a[i] = sc.nextInt();
}
int[] d = new int[n+1];
for (int i=1; i<=n; i++) {
d[i] = -1;
for (int j=1; j<=i; j++) {
if (d[i] == -1 || d[i] > d[i-j] + a[j]) {
d[i] = d[i-j] + a[j];
}
}
}
System.out.println(d[n]);
}
}
코드설명
참고 :
출처 : https://www.acmicpc.net/problem/16194
Author And Source
이 문제에 관하여(백준 16194 / 카드 구매하기 2), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dogit/백준-16194-카드-구매하기-2저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)