[백준] 15817: 배수 공사 - JAVA

02 Nov 2023 in Algorithm on 다이나믹 프로그래밍

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

풀이

파이프의 길이와 각 길이 파이프들의 개수가 주어진다.

이 파이프들을 갖고 x길이를 만드는 문제이다.

길이가 짧은것부터 주어지므로 따로 정렬할 필요는 없었다.

길이가 짧은 파이프부터 보면서 x부터 0으로 내려가면서 역순 탐색을 통해 dp배열에 값을 누적시켰다.

---

메모리: 14324KB

시간: 232ms

언어: Java 11

코드

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

public class Main {
    static class Pipe {
        int length;
        int count;

        public Pipe(int length, int count) {
            this.length = length;
            this.count = count;
        }
    }

    public static void main(String[] args) throws Exception {
        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());

        Pipe[] arr = new Pipe[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            arr[i] = new Pipe(l, c);
        }

        int[] dp = new int[x + 1];
        dp[0] = 1;
        for (int i = 0; i < n; i++) {
            int len = arr[i].length;
            int cnt = arr[i].count;

            for (int j = x; j >= 0; j--) {
                for (int k = 1; k <= cnt && j - k * len >= 0; k++) {
                    dp[j] += dp[j - k * len];
                }
            }
        }

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

}