[code.plus 알고리즘 기초] no. 11052

https://www.acmicpc.net/problem/11052

좋지 못한 접근 방법

dp(dynamic programming)문제는 이전의 있는 값을 활용해서 풀어야한다.

무턱대고 직관적인 방식으로 풀다가는 꼬이기도 쉽고 런타임 시간과 푸는 시간도 오래 걸릴 것이다.

올바른 접근 방법

package n11052;
 
import java.util.Scanner;
 
public class Main {
    public static int result = 0;
 
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n+1]; // price 배열
 
        for (int i=1; i<=n; i++) {
            a[i] = sc.nextInt();
        }
 
        int[] d = new int[n+1]; // 최대값 저장
 
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=i; j++) {//dp[n]을 max값 비교하기 위해 총 n번 검사
                if (d[i] < d[i-j] + a[j]) { // max 값 비교
                    d[i] = d[i-j] + a[j];// 사는 경우의 수( 카드를 1개 살때부터 n개 살때까지
                }
            }
        }
        System.out.println(d[n]);
    }
}