[백준] 2073 수도배관공사

1. 문제

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

2073번: 수도배관공사

2. 접근방법

1. dp배열 생성

2. 각 컬럼은 배관의 길이

3. 값은 그 길이를 만들 수 있는 값 중 최대값

4. dp 계산은 역순으로 진행

5. 이전 값은 현재 값에 영향을 주지만 더 큰 값은 현재값에 영향을 주지 않으므로 역순으로 진행 시 배열 하나에서 진행가능

6. 각 길이에서 현재 파이프를 연결시켜보기

7. dp [ 각 길이 - 현재 파이프 길이 ] 의 값과 현재 파이프 값 중 작은 값

8. 7번의 값과 현재 만들어진 최대값 dp[ 각 길이 ] 중 큰 값을 dp에 저장

9. dp[목표길이] 값 출력

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class G5_2073수도배관공사 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int D = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		int dp[] = new int[D + 1];
		dp[0] = Integer.MAX_VALUE;
		for (int i = 0; i < P; i++) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			for (int j = D; j >= l; j--)
				dp[j] = Math.max(dp[j], Math.min(dp[j - l], c));
		}
		System.out.println(dp[D]);
	}
}

4. 마치며

dp 설명 어려워ㅓ