데일리썽

문제 제목 : 기타리스트

난이도 : 중

문제 유형 : 동적 프로그래밍(DP

추천 풀이 시간 : 40분 (못하면 2배 80분)

TIP : 가장 적은 경우의 수부터 계산을 해본 후 패턴을 찾아 점화식을 세우자@@

점화식이란? 이웃하는 두개의 항 사이에 성립하는 관계를 나타낸 관계식 예를들어 dp[n + 2] = dp[n + 1] + dp[n + 2]

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        Integer n = sc.nextInt();
        Integer s = sc.nextInt();
        Integer m = sc.nextInt();
        ArrayList<Integer> diffList = new ArrayList<Integer>();
        int[][] dp = new int[51][1001];
        
        for (int i = 0; i < n; i++) {
            diffList.add(sc.nextInt());
        }
        
        dp[0][s] = 1;
        
        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < m + 1; j++) {
                if (dp[i - 1][j] == 0) continue;
                if (j - diffList.get(i - 1) >= 0) {
                    dp[i][j - diffList.get(i - 1)] = 1;
                }
                if (j + diffList.get(i - 1) <= m) {
                    dp[i][j + diffList.get(i - 1)] = 1;
                }
            }
        }
        
        int result = -1;
        for (int i = m; i >= 0; i--) {
            if (dp[n][i] == 1) {
                result = i;
                break;
            }
        }
        
        System.out.println(result);
    }
}