DP문제풀이

1,2,3 더하기

• 정수 n을 1,2,3의 조합으로 나타내는 방법의 수를 구하는 문제

• x + x + … + x = n; 마지막x에 올 수 있는 수 : 1,2,3중 하나

• case1 : 마지막 x = 1일때, 이전의 합 : n-1 => D[n-1]
• case2 : 마지막 x = 2일때, 이전의 합 : n-2 => D[n-2]
• case3 : 마지막 x = 3일때, 이전의 합 : n-3 => D[n-3]
• D[n] = D[n-1] + D[n-2] + D[n-3];

import java.util.Scanner;

public class Baekjoon2193 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        long [] arr = new long[num+1];
        arr[1] = 1;
        arr[2] = 1;
        for (int i = 3; i <= num; i++)
            arr[i] = arr[i-1] + arr[i-2];

        System.out.println(arr[num]);
    }
}

붕어빵 판매하기(백준11052)

• 붕어빵 N개를 가지고 있다. i개를 팔아서 얻을 수 있는 수익이 p[i]일 때, N개를 모두 판매해서 얻을 수 있는 최대 수익구하기
• 2개를 팔아서 수익이 5원이면, 2개를 팔아서 5원이지, 1개를 팔아서 5원이아니다.

4 // 4개
1 5 6 7 // p[1] = 1, p[2] = 5, p[3] = 6, p[4] = 7

정답은 10 => 2개를 팔면 5원이 되기때문에 2개씩 2번팔면 총 10원이 된다.

5 // 5개를 팔때,
10 9 8 7 6

// 정답은 50, 1개씩 5번팔기

4
3 5 15 16
// 정답 18원

• D[n] : n개팔아서 얻을 수 있는 수익
• x + x + x + x … + x = n;

• 마지막사람한태 붕어빵을 몇개를 팔 수 있는지를 결정한테

• case1 마지막사람에게 1개를 팔때, 이전사람에게 팔 수 있는 붕어빵 n-1개, 최대수익은 : D[n-1], 한명한테 얻을 수 있는 수익은 : p[1], 총 수익 : D[n-1]+P[1]

• case2 마지막사람에게 2개를 팔때, 이전사람에게 팔 수 있는 붕어빵 n-2개, 최대수익은 : D[n-2], 한명한테 얻을 수 있는 수익은 : p[2], 총 수익 : D[n-2]+P[2]

• 일반화 : max(P[i] + P[n-i]); 1<=i<=n;

for (int i=1; i<=n; i++) {
	for (int j=1; j<=i; j++) {
    	d[i] = max(d[i], d[i-j]+a[j]);
    }
}