[백준] 11052: 카드 구매하기

강은서·2022년 1월 29일
0

백준

목록 보기
17/21
post-thumbnail

문제

문제 풀이

N개를 사는 경우
처음에 N개가 들어있는 카드팩을 사는 경우와 N-1개를 가장 비싼 값에 사는 경우(dp[N-1])와 1개가 들어있는 카드팩을 사는 경우를 합한 값과(dp[N-1] +1) 비교하여 dp값을 정한다.

이후 마찬가지로 N-2개를 가장 비싼 값에 사는 경우(dp[N-2])와 2개가 들어있는 카드팩을 사는 경우를 합한 것(dp[N-2] + 2)과 dp[N]을 비교하여서 큰 값을 가진 것을 dp[N]값을 정한다.

코드

import java.util.Scanner;

public class ANS11052 {

    static int N;
    static int[] dp, cost;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        //dp, cost 선언 및 초기화
        dp = new int[N+1];
        cost = new int[N+1];
        for(int i = 1 ; i <= N; i++){
            cost[i] = sc.nextInt();
        }

        dp[0] = 0;
        for(int i = 1; i <= N; i++){
            for(int j = 1; j <= i; j++){
                dp[i] = Math.max(dp[i], dp[i-j] + cost[j]);
            }
        }

        System.out.println(dp[N]);
    }
}

0개의 댓글