수도배관공사2073

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

DP문제는 어렵다.. 새로운 문제가 나올때마다 풀 수 있는 방법이 떠오르지 않는다 이번 문제는 DP문제인지도 몰랐다;;

코드 풀이
dp 배열의 인덱스는 길이. 값은 용량이다.
특정 길이를 만드는데 최대의 용량은 얼마인가를 저장하는것이다

dp[0] = 인트변수의 최대값으로 해놓는다. 코드를 보면 알 수 있는데
파이프를 하나만 사용해서 특정길이를 만들때 즉 파이프 길이가 5 일때 
dp[5]에 파이프의 용량을 저장하기 위함이다. 물론 dp[5]가 아직 초기에 0으로 
되있을때만 저장하는것이고 dp[5]에 이미 값이 있으면 용량이 더 큰 값을 비교해서 
저장하게 된다

목표길이가 7이라고 해보자 파이프길이와 용량을 하나씩 파싱하면서 다음의 로직을 실행한다
목표는 7 인데 현재 파싱된 파이프가 3이고 용량은 4라고 해보자
그럼 우선 7의 길이를 만드려면 파이프4가 필요하겠다. 그렇다면 4와 3의 용량을 비교해야한다

dp[7-3] => 현재 dp[4]의 용량을 구해서
4(현재파이프용량)과 비교해야한다.
그리고 둘중에 작은 용량이 선택된다. 그 코드가 Math.min(dp[j-l], c) 이다.
새로운dp[7]의 용량이라고 볼 수 있다.
그리고 올드dp[7]와 새로운 dp[7]을 비교해서 더 큰 값을 dp[7]에 넣는다
그 코드가 dp[j] = Math.max(dp[j], Math.min(dp[j-l], c)); 이다
근데 초기에 dp[0]을 제외하면 전부 dp배열의 값은 0이므로 dp[7]에 0이 저장될 것이다

그리고 다음 목표길이 6에도 똑같은 작업이 반복되고 dp[6]에도 0저장된다. 반복 반복 된다. 그러다가
dp[3] 에는 현재 파싱된 파이프의 용량 4가 세팅될 것이다.

그리고 새로운 파이프를 파싱하게 될것이고 그러다 보면 dp[j] 에 용량이 세팅될것이고 새로운 파이프 + 기존 파이프 로 만든 용량과 비교해서 큰 값이 dp[j] 에 세팅될것이다

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");

        int D = Integer.parseInt(input[0]);
        int P = Integer.parseInt(input[1]);

        int[] dp = new int[D+1];
        dp[0] = Integer.MAX_VALUE;

        for (int i = 0; i < P; i++) {
            input = br.readLine().split(" ");

            int l = Integer.parseInt(input[0]);
            int c = Integer.parseInt(input[1]);

            for (int j = D; j >= l; j--) {
                dp[j] = Math.max(dp[j], Math.min(dp[j-l], c));
            }
        }

        System.out.println(dp[D]);
    }
}