[백준] 15817 배수공사 - Java

 

 

 

문제 출저

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

15817번: 배수 공사

 

 

 

문제 풀이

파이프 종류 수 N과 합친 파이프의 길이 x가 주어집니다. 

N 종류의 파이프의 길이는 L과 수량 C가 주어집니다. x를 만들 수 있는 경우의 수를 구해야 합니다.

 

dp를 이용해 문제를 풀었습니다. 

파이프 종류를 이용해 만들 수 있는 길이를 업데이트 합니다.

 

주의점

x는 12이고 4의 파이프가 3개 있다고 가정합니다.

그러면 dp[4] = 1, dp[8] = 1, dp[12] = 1 이 되어야 합니다. 

제가 기존에 풀었던 방식은 현재 파이프의 길이의 dp를 +1하고 x부터 파이프의 길이까지 탐색했습니다.

for(int i = 1; i <= c; i++) {
	int length = 4 * i; 
    if(length > x) continue;  
    dp[length] += 1;
    for(int j = x; j > length; j--) {
    	dp[j] += dp[j - length]; 
    }
}

 

하지만 이런 식으로 진행하면 중복이 발생합니다. 4에서 dp[4] = 1이 되고 8에서 dp[4+8] = 1이 되고 dp[12] += 1이 되면서 dp[12] = 2가 됩니다.

이 문제를 해결하기 위해 2개의 int 배열을 사용했습니다. 

int[] beforeDp; int[] afterDp; 

하나의 종류의 파이프를 탐색할 때 before를 보고 after를 업데이트 하는 형식으로 중복을 줄였습니다. 

 

 

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

/*
배수공사
https://www.acmicpc.net/problem/15817
 */

public class Main {

    static int n, x;
    static int[] beforeDp;
    static int[] afterDp;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());

        beforeDp = new int[x + 1];
        afterDp = new int[x + 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 = 1; j <= c; j++) {
                int length = l * j;

                if (length > x) continue;

                for (int k = x; k > length; k--) {
                    afterDp[k] = afterDp[k] + beforeDp[k-length];
                }

                afterDp[length] += 1;

            }

            for (int j = 0; j <= x; j++) {
                beforeDp[j] = afterDp[j];
            }

        }


        System.out.println(afterDp[x]);



    }

}

 

 

 

문제를 풀고 다른 사람의 코드를 참조했습니다. int 배열 하나로 문제를 해결하는 방식이었습니다. 

제가 중복을 발생한 이유는 dp[length] += 1 하는 방식이었기 때문입니다.

하지만 dp[0] = 1로 하면 문제는 해결합니다. 

 

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

public class Main {

    static int n, x;
    static int[] dp;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        x = Integer.parseInt(st.nextToken());
        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--) {
                for (int k = 1; k <= c; k++) {
                    int length = l * k;
                    if (length > j) break;
                    dp[j] += dp[j-length];
                }
            }


        }


        //System.out.println(Arrays.toString(dp));
        System.out.println(dp[x]);



    }

}

 

 

 

후기

매일 꾸준히 문제를 풀고 있지만 더 나은 실력 향상을 위해서는 역시 고수의 코드를 보는 것이 도움이 된다는 것을 다시 한 번 느꼈습니다.