*경우는 두 가지가 있습니다. (더하기 , 뺴기)
*조건에 따라서 필터링 해줍니다 (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 |