[11052]붕어빵 판매하기

문제

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

풀이

D[i]이 i개를 팔 때 얻을 수 있는 최대 수익

P[i]는 i개를 팔 때 얻는 수익

총 붕어빵이 i개 있을 때

1개를 팔았을 때 최대값은 P[1] + D[i-1]

2개를 팔았을 때 최대값은 P[2] + D[i-2]

j개를 팔았을 때 최대값은 P[j] + D[i-j]

이렇게 따져서 이들 값중에서 최대값이 D[i]

점화식을 살펴보면

D[i] = max(P[j] + P[i-j])

단, j의 범위는 1<= j <= i

이를 바탕으로 코딩을 해보면 된다.

import java.util.Scanner;
 
public class Main {
    static int[] d = new int[1001];
    static int[] p = new int[10001];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i=1;i<=n;i++) {
            p[i] = scan.nextInt();
        }
        System.out.println(maxIn(n));
        scan.close();
    }
    
    static int maxIn(int n) {
        if(d[n]>0) return d[n];
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=i;j++) {
                d[i] = Math.max(d[i],maxIn(i-j)+p[j]);
            }    
        }
        return d[n];
    }
}

#아직 프로그래밍적 사고와 다이나믹 프로그래밍적 문제 접근 방식이 익숙하지 않은것 같다.