문제보기


*경우는 두 가지가 있습니다. (더하기 , 뺴기)

*조건에 따라서 필터링 해줍니다 (0보다 커야됩니다.)

*2차원으로 만들어 값을 체크하면서 진행합니다. 

 -> D[N][M]    

*곡 연주가 가능하다면 배열의 해당칸에 1을 넣어줍니다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package Problems;
 
/**
 * 
 * 백준 1495 dp
 *
 */
import java.util.Scanner;
 
public class Boj1495dp {
 
    public static int n, s, m;
 
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        s = in.nextInt();
        m = in.nextInt();
        int max = -1;
        int[][] arr = new int[n + 1][m + 1];
 
        int[] v = new int[n + 1];
 
        for (int i = 1; i <= n; i++) {
            v[i] = in.nextInt();
        }
        arr[0][s] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= m; j++) {
                if (arr[i-1][j] == 1) {
                    if (j + v[i] > m && j - v[i] < 0) {
                        continue;
                    }
 
                    if (j + v[i] <= m) {
                        arr[i][j + v[i]] = 1;
                    }
 
                    if (j - v[i] >= 0) {
                        arr[i][j - v[i]] = 1;
 
                    }
 
                }
 
            }
        }
 
        int result = -1;
        for (int j = 0; j <= m; j++) {
            if (arr[n][j] == 1) {
                if (result < j) {
                    result = j;
                }
            }
        }
 
        System.out.println(result);
 
    }
 
}
 
cs


'알고리즘(추가예정) > 동적계획법' 카테고리의 다른 글

백준 2315 가로등 끄기  (0) 2017.11.16
백준 1563 개근상  (0) 2017.11.14
백준 11048 이동하기  (0) 2017.11.08
백준 1912 연속합  (0) 2017.11.07
백준 11055 가장 큰 증가하는 부분수열  (0) 2017.11.07

+ Recent posts