11052번: 카드 구매하기
첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)
www.acmicpc.net
카드 구매하기 입니다. 문제에서는 최대한 비싼 가격으로 카드를 구매해야하기 아래의 배열부터 올라와서 높은 값을 갱신해 주어야 합니다. 따라서 아래에서 부터 최대값을 갱신해주어야 합니다.
package com.company;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int t = Integer.parseInt(br.readLine());
long dp[] = new long[t+1];
long number[] = new long[t+1];
st = new StringTokenizer(br.readLine());
for(int i = 1; i<=t; i++){
number[i] = Integer.parseInt(st.nextToken());
}
for(int i =1; i<=t; i++){
for(int j = 1; j<=i; j++){
dp[i] = Math.max(dp[i], dp[i-j] + number[j]);
}
}
System.out.println(dp[t]);
}
}
부족했던 점
처음에는 다음과 같은 점화식을 사요했습니다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
int t = Integer.parseInt(br.readLine());
long dp[] = new long[t+1];
long number[] = new long[t+1];
st = new StringTokenizer(br.readLine());
for(int i = 1; i<=t; i++){
number[i] = Integer.parseInt(st.nextToken());
}
dp[1] = number[1];
if(t>1){ dp[2] = Math.max(number[2],dp[1]*2);}
if(t>2){dp[3] = Math.max(number[3], number[1] +dp[2]);}
for(int i =4; i<=t; i++){
dp[i] = Math.max(number[i], Math.max(dp[i-1]+number[1], dp[i-2]+dp[2]));
}
System.out.println(dp[t]);
}
}
하지만 코드는
1 100 160 1 1 1 1 1 1 1 의 반례가 존재하였습니다.
해당 케이스의 답은 520이 나와야 하지만 제가 구성한 위의 코드는 최대값이 500이 나왔습니다.
'C++ > DP' 카테고리의 다른 글
DP - 2225(합분해) (0) | 2021.01.16 |
---|---|
DP - 9461(파도반 수열) (0) | 2021.01.16 |
DP-2133(타일 채우기) (0) | 2021.01.16 |
DP-1699(제곱수의 합) (0) | 2021.01.16 |
DP - 2579_계단 오르기 (0) | 2021.01.13 |