[BOJ][#DP]15817번 배수 공사

배수 공사

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

955

360

303

41.057%

문제

영만이네 집은 너무 오래되어서 변기에 물이 줄줄 샌다. 보다 못한 영만이는 마침 집에 파이프가 남아 있어서 직접 배수 공사를 하려고 한다.

하지만 파이프를 자르는 비용이 너무나 비싸기 때문에, 가난한 영만이는 남은 파이프들을 적절히 모아서 원하는 길이로 만들어야 한다. 

영만이가 가지고 있는 파이프의 길이와 그 수량을 알고 있을 때, 파이프를 적당히 합쳐서 x만큼의 길이를 만드는 방법의 수를 구하시오. 파이프를 합치는 순서는 고려하지 않는다.

입력

영만이가 가지고 있는 파이프의 종류의 수 N과 만들고 싶은 합친 파이프의 길이 x가 주어진다. (1 ≤ N ≤ 100 이며, 1 ≤ x ≤ 10 000 이다.)

다음 N개의 줄에 걸쳐서 파이프의 길이 Li 와 수량 Ci 이 공백을 사이에 두고 주어진다. 길이가 짧은 것부터 순서대로 입력되며, 0 < Li ≤ x, 0 < Ci ≤ 100 이다. 또한, 입력되는 파이프의 길이는 서로 다르다.

출력

합친 파이프의 길이 x를 만들 수 있는 방법의 수를 출력한다. 방법의 수가 2,147,483,647를 넘는 경우는 없다.

예제 입력 1 복사

3 20
4 3
6 3
9 2

예제 출력 1 복사

1

---

📝풀이

이 문제는 **동적 계획법(DP)**을 활용하여 주어진 파이프들로 원하는 길이를 만드는 경우의 수를 구하는 문제입니다. 핵심은 중복 갱신을 방지하며 각 파이프와 그 개수를 효과적으로 처리하는 것입니다.

 

 

• DP 배열 초기화
  • dp[i]는 길이 iii를 만드는 방법의 수를 저장합니다.
  • 처음에는 아무것도 하지 않는 경우가 1개 존재하므로, dp[0] = 1로 초기화합니다.
• 역순 갱신을 통해 중복 방지
  • 역순으로 반복하면서 갱신해야 중복 갱신을 피할 수 있습니다.
  • 순방향 갱신에서는 갱신된 값을 참조하여 다른 결과를 덮어쓰는 문제가 생기지만, 역순으로 진행하면 기존 값을 기준으로만 갱신합니다.
• 파이프 개수 CCC만큼 반복
  • d×L의 형태로 파이프 L을 최대 C개까지 사용할 수 있으므로, 1≤d≤C에 대해 d×L씩 더하면서 dp를 갱신합니다.
  • dp[j]가 0이면 연산을 생략해 성능을 최적화합니다

 

 

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

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        int dp[] = new int[x+1];
        dp[0] = 1;

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken()); 
            int C = Integer.parseInt(st.nextToken()); 
            
            for (int j = x; j >= 0; j--) {
                if (dp[j] > 0) {
                    for (int d = 1; d <= C; d++) {
                        int target = j + d * L;
                        if (target <= x) {
                            dp[target] += dp[j];
                        }
                    }
                }
            }

        }

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