11052번(카드 구매하기)

첫 시도

• N이 1000이므로 O(N^2)까지는 가능
• 카드 N개를 구매할 때 금액이 클수록 좋다.

해결

• • N이 3이라고 했을 때 결과가 3이 되는 계산식은 3 = 3, 3 = 2 + 1, 3 = 1 + 2, 3 = 1 + 1 + 1이고 각 계산식 마다 소비될 금액의 최대값을 N에 저장해주면서 증가시키면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());

        int[] input = new int[N+1];
        int[] dp = new int[N+1];

        for (int i = 1; i < N+1; i++) {
            input[i] = Integer.parseInt(st.nextToken());
        }
        dp[0] = 0;

        for(int i =1; i<N+1; i++){
            for(int j = 1; j<=i; j++){
                dp[i] = Math.max(dp[i],input[j]+dp[i-j]);
            }
        }
        System.out.println(dp[N]);

    }
}

참고

• https://developer-mac.tistory.com/69 -https://dreamingdreamer.tistory.com/157