아이디어

• memo[i][j]를 "$0$~$i$번째 파이프까지 봤을 때 파이프 총 길이가 $j$가 되는 경우의 수"로 정의하자.
• 관찰
  1. 이전 차례($i$-루프)의 memo값은 유지된다.
  2. 추가로 $k$=$1$~$C_i$에 대해 이전 차례에서 총 길이가 $j-L_ik$가 되는 경우의 수를 그대로 취할 수 있다.
• 한편, 위의 관찰 1번은 $k=0$일 때 총 길이가 $j$로 이어지는 경우로 보아 두 경우를 $k=0$~$C_i$로 생각할 수 있다.
• 아무것도 고르지 않았을 때 길이 합이 $0$이 된다는 점에서 초기값을 memo[0][0] = 0로 잡을 수 있다.
• $i$-$j$ 순서로 2중 루프를 돌며 memo를 모두 채우면, 구하는 정답은 memo[N][x]가 된다.

코드

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

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int N, x;
    static int[] L, C;

    static int[][] memo;    // memo[i][j] = i번 파이프까지 봤을 때 길이가 j가 되는 경우의 수

    public static void main(String[] args) throws Exception {
        tk = new StringTokenizer(rd.readLine());
        N = Integer.parseInt(tk.nextToken());
        x = Integer.parseInt(tk.nextToken());

        L = new int[N+1];
        C = new int[N+1];
        memo = new int[N+1][x+1];

        for (int i=1; i<=N; i++) {
            tk = new StringTokenizer(rd.readLine());
            L[i] = Integer.parseInt(tk.nextToken());
            C[i] = Integer.parseInt(tk.nextToken());
        }

        // process
        memo[0][0] = 1;

        for (int i=1; i<=N; i++) {                  // item idx
            for (int j=0; j<=x; j++) {              // current total length
                for (int k=0; k <= C[i]; k++) {     // number of pipe i to contain
                    int lk = L[i] * k;
                    if (j >= lk) {
                        memo[i][j] += memo[i-1][j-lk];
                    }
                }
            }
        }

        System.out.println(memo[N][x]);
    }
}

메모리 및 시간

• 메모리: 18268 KB
• 시간: 340 ms

리뷰

• 파이프가 1개가 아닌 여러 개일 수 있다는 배낭 문제의 응용
• DP는 메모이제이션의 정의가 가장 중요하다는 것을 상기하자.

수정 (24.10.09. 04:55)

• 매 $i$-루프마다 $i-1$행과 $i$행만 참조하는 것을 이용해 memo 배열을 $N$행에서 $2$행으로 줄일 수 있다.
  • 공간복잡도: $O(Nx) \to O(x)$
• 수정된 부분

// ...

memo = new int[2][x+1];  // [N+1]에서 [2]로 바뀜

// ...

for (int i=1; i<=N; i++) {
	for (int j=0; j<=x; j++) {
    	memo[i%2][j] = 0;					// [i]에서 [i%2]로 바뀜
        for (int k=0; k <= C[i]; k++) {
         	int lk = L[i] * k;
        	if (j >= lk) {
            	memo[i%2][j] += memo[1-i%2][j-lk]; // [i] -> [i%2], [i-1] -> [1-i%2]
            }
        }
	}
}

• 단, 모듈로 연산의 추가로 시간이 약간 증가한 것을 볼 수 있다.
• 메모리: 18072 KB, 시간: 428 ms