DP - 11052(카드구매하기)

11052번: 카드 구매하기 (acmicpc.net)

11052번: 카드 구매하기

 

카드 구매하기 입니다. 문제에서는 최대한 비싼 가격으로 카드를 구매해야하기 아래의 배열부터 올라와서 높은 값을 갱신해 주어야 합니다. 따라서 아래에서 부터 최대값을 갱신해주어야 합니다. 

 

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이 나왔습니다.