[DP 0-1 knapsack][백준 2616] 소형기관차

기차는 맨 앞에 있는 기관차 1대가 손님이 탄 객차 여러 칸을 끌고 간다. 기관차가 고장 나면 기차를 운행할 수 없게 되므로 최근 철도청은 기관차 고장에 대비하여 몇몇 역에 소형 기관차 3대를 배치하기로 결정하였다. 소형 기관차는 평소에 이용하는 기관차보다 훨씬 적은 수의 객차만을 끌 수 있다.

기관차가 고장났을 때 끌고 가던 객차 모두를 소형 기관차 3대가 나누어 끌 수 없기 때문에, 소형 기관차들이 어떤 객차들을 끌고 가는 것이 좋을까 하는 문제를 고민하다가 다음과 같이 하기로 결정하였다.

1. 소형 기관차가 최대로 끌 수 있는 객차의 수를 미리 정해 놓고, 그보다 많은 수의 객차를 절대로 끌게 하지 않는다. 3대의 소형 기관차가 최대로 끌 수 있는 객차의 수는 서로 같다.
2. 소형 기관차 3대를 이용하여 최대한 많은 손님을 목적지까지 운송하도록 한다. 각 객차 마다 타고 있는 손님의 수는 미리 알고 있고, 다른 객차로 손님들이 이동하는 것은 허용하지 않는다.
3. 각 소형 기관차는 번호가 연속적으로 이어진 객차를 끌게 한다. 객차는 기관차 바로 뒤에 있는 객차부터 시작하여 1번부터 차례로 번호가 붙어있다.

예를 들어 기관차가 끌고 가던 객차가 7칸이고, 소형 기관차 1대가 최대로 끌 수 있는 객차 수는 2칸이라고 하자. 그리고 1번부터 7번까지 각 객차에 타고 있는 손님의 수가 아래 표와 같다고 하자. 괄호 속에 있는 숫자는 객차 번호를 나타낸다.

 

소형 기관차 3대는 각각 1-2번, 3-4번, 그리고 6-7번 객차를 끌고 가면 손님 240명을 운송할 수 있고, 이보다 많은 수의 손님을 운송할 수 없다.

기관차가 끌고 가던 객차의 수와 각 객차에 타고 있던 손님의 수, 그리고 소형 기관차가 최대로 끌수 있는 객차의 수가 주어질 때, 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 구하는 프로그램을 작성하시오

첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있는 손님의 수는 100명 이하이고, 입력되는 숫자들 사이에 빈칸이 하나씩 있다. 셋째 줄에는 소형 기관차가 최대로 끌 수 있는 객차의 수가 입력된다. 그 수는 기관차가 끌고 가던 객차 수의 1/3보다 적다.

출력

한 줄에 소형 기관차 3대를 이용하여 최대로 운송할 수 있는 손님 수를 출력한다

 

 

풀이

1. 부르트포스

각 칸마다 소형기관차를 태울지 말지 선택 -> O(2^1000)  시간초과 

 

2. 0-1 냅색 

dp[n][k]: n번째 칸, k번째 소형기관까지 고려 시 최대한 많은 인원은? 

공간복잡도: O(10^6), 시간 복잡도: O(10^6) 모두 통과

단, n번째 칸에서 소형기관차를 선택한다면, n번째 칸은 소형기관차의 마지막 칸이라 가정! 

 

 

잘못 생각했던 범위 수정 과정

 

 

 

문제 예시 DP 풀이

 

코드 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int K = Integer.parseInt(br.readLine());
        int[][] dp = new int[N + 1][4];

        for (int i = K; i <= N; i++) {
            for (int t = 1; t <= 3; t++) {
                int pre = i - K + 1;

                // 기관차 선택 안함
                dp[i][t] = Math.max(dp[i][t], dp[i-1][t]);
                
                // 기관차 선택
                if (pre >= 1) {
                    int val = 0;	// 인구 계산
                    for(int a = pre ; a <= i ; a++) {
                        val += arr[a];
                    }
                    dp[i][t] = Math.max(dp[i][t], dp[i - k][t - 1] + val);
                }
            }
        }

		// dp 과정 확인
//        for (int i = 0; i <= N; i++) {
//            for (int t = 0; t <= 3; t++) {
//                System.out.print(dp[i][t] + " ");
//            }
//            System.out.println();
//        }


        System.out.println(dp[N][3]);
    }
}