[BJ] 2616 - 소형기관차

안녕하세요, Einere입니다.

(ADblock을 꺼주시면 감사하겠습니다.)

---

이번 포스트에서는 백준 Q2616 - 소형기관차에 대해 포스팅하겠습니다.

 

 

접근 방법

최대한 많은 승객을 싣게 했을 때, 그 승객의 수를 출력하는 문제입니다. 욕심덩어리 기관차네요. 이렇게 특정 조건을 만족하면서 최대 혹은 최소와 관련된 문제가 나온다면 탐욕(greedy) 알고리즘인 경우가 많으며, 또한 탐욕 알고리즘과 같이 딸려오는 개념이 동적 프로그래밍(dynamic programming)이죠. 물론 해당 문제의 분류는 DP입니다.

저는 이 문제를 보고 0-1 knapsack 문제와 매우 유사하다고 생각했습니다. 어찌됬건 각 객차를 선택하거나 선택하지 않거나로 나눌 수 있기 때문이죠. (기타 자잘한 부분은 각종 제약조건으로 검사할 수 있습니다.)

따라서 제가 생각하는 키 포인트는 다음과 같습니다.

• 0-1 : 각 객차는 선택하거나, 선택하지 않습니다. 객차를 쪼개서 일부 승객만 운송할 수 없습니다.
• DLS(depth limited search) : 문제에서 객차의 수는 정해져 있으므로, 탐색해야 할 깊이는 고정되어 있습니다.
• DFS, BFS : DLS이므로 둘 중 어느것을 써도 해를 반드시 찾을 수 있습니다만, 문제 특성상 모든 객차를 탐색해 봐야 우리가 원하는 최종 승객의 수를 얻을 수 있으므로 DFS를 추천합니다.
• BT(back tracking) : 만약 최적의 해를 찾지 못했다면, 뒤로 돌아가서 다른 자식 노드를 탐색해야 합니다. 따라서 각 함수마다 고유한 상태를 가져야 합니다. (즉, 전역 변수를 변경하는 것을 최대한 지양해야 합니다.)
• DP : 일단 분류는 DP입니다. 실제로 DLS로 풀어보니 시간초과가 나네요.

 

 

DP

동적 계획법은 다양한 특성을 가지고 있습니다.

• DC(devide & conquer)를 활용하여 문제를 작게 분할한 뒤, 작은 문제를 풀고 합쳐서 최종 문제를 풉니다. 그래서 보통 문제를 점화식으로 표현할 수 있습니다.
• 점화식의 특성 상, 중복된 항이 자주 출현하게 됩니다.(피보나치 수열이 대표적입니다.) 작게 쪼개진 문제가 중복되는 경우를 대비하여, 최적화를 위해 memoization(메모이제이션)을 활용합니다.
• 작게 쪼개진 문제를 먼저 푼 뒤, 합쳐나가는 과정을 수행하므로 bottom-up방식이라고 할 수 있습니다.
• 시간에 따라 상태가 변하지 않는 문제에 대해 최적의 해를 구할 수 있습니다. (즉 재귀함수가 호출될 때 마다 상태가 변한다면 최적의 해를 구할 수 없습니다.)
• 모든 경우의 수를 일일이 확인하므로 BF(brute force)와 유사합니다.

 

 

DP 풀이 로직

• bottom-up방식을 사용합니다. 즉 소형기관차가 0개, 선택할 객차 번호가 0번인 경우부터 시작합니다. (물론 소형기관차가 0개인 경우 아무 객차도 끌 수 없으므로 최대 승객수는 모두 0이 됩니다.)
• DLS와 같이, 해당 객차를 선택할지 안할지 두가지의 경우가 있습니다. 그러나, 여기서 최적의 해(둘 중의 하나)를 기억합니다.
• 표를 채워보면서 점화식을 구합니다.

위 표는 문제의 점화식을 구하기 위한 표입니다.

우선 변수로서 totalCoachNumber(최대 객차 수), passengers(각 객차 별 탑승 승객 수), maxSmallTrain(최대 소형기관차의 수), maxCoachNumber(한 소형기관차가 끌 수 있는 최대 객차 수)가 있습니다.

그리고 DP라는 이름의 2차원 배열이 있습니다.

DP를 채우는 로직은 다음과 같습니다.

• 해당 객차 이후의 객차들은 생각하지 않습니다.
• 해당 객차를 선택하는 경우 :
  
  • 선택한 객차를 끌 소형기관차는 최대한 많은 객차를 끌어야 하므로, c번 객차부터 c - maxCoachNumber + 1번 객차까지 첫번째 소형기관차가 끌었을 때의 승객 수(sum(c - maxCoachNumber + 1, c))를 구합니다.
  • 첫번째 소형기관차는 자신이 끌고 갈 객차를 모두 선택했으므로, 첫번째 소형기관차를 제외한 나머지 소형기관차와 첫번째 소형기관차가 끌고 간 객차들을 제외한 객차에 대해 최대로 끌 수 있는 승객 수(DP[r - 1][c - maxCoachNumber])를 구합니다. 이 값은 최적의 해임을 보장합니다.
  • 두 승객 수를 합친 수(DP[r - 1][c - maxCoachNumber] + sum(c - maxCoachNumber + 1, c))를 구합니다.
• 해당 객차를 선택하지 않는 경우 : 
  • 해당 객차를 제외하고, 바로 이전 객차에 대한 최대 승객 수(DP[r][c - 1])를 그대로 가져옵니다.

한번 예시를 들어볼까요?

소형기관차가 1개인 경우, 첫번째 객차에 대해 생각해봅시다. 소형기관차는 최대 2개의 객차를 끌 수 있으므로, 객차를 하나만 끈다면 최적의 해가 아니므로 DP[1][1] = 0이 됩니다.

이제 두번째 객차에 대해 생각해봅시다. 해당 객차를 선택하는 경우, 최대로 끌 수 있는 승객의 수는 35 + 45 = 75명 입니다. 그리고 해당 소형기관차를 제외한 소형기관차는 없으므로 나머지 소형기관차는 0명을 끄는 것과 동일합니다. 따라서 0 + 75 = 75입니다. 그러나 해당 객차를 선택하지 않는 경우, 바로 이전의 객차에 대한 최대 승객수는 0명입니다. 0보다 75가 크므로 DP[1][2] = 75가 됩니다.

세번째 객차에 대해 생각해봅시다. 해당 객차를 선택하는 경우, 최대로 끌 수 있는 승객의 수는 40 + 50 = 90명 입니다. 그리고 해당 소형기관차를 제외한 소형기관차는 없으므로 나머지 소형기관차는 0명을 끄는 것과 동일합니다. 따라서 0 + 90 = 90입니다. 그러나 해당 객차를 선택하지 않는 경우, 바로 이전의 객차에 대한 최대 승객수는 75명입니다. 75보다 90이 크므로 DP[1][3] = 90이 됩니다.

 

그럼 이제 소형기관차가 2개인 경우, 세번째 객차에 대해 생각해봅시다. 해당 객차를 선택하던지 말던지 소형기관차 중 하나는 1개의 객차밖에 끌 수 없으므로 최적의 해가 될 수 없습니다. 따라서 DP[2][3] = 0입니다.

네번째 객차에 대해 생각해봅시다. 해당 객차를 선택하는 경우, 최대로 끌 수 있는 승객의 수는 50 + 10 = 60명이며, 첫번째 소형기관차를 제외한 나머지 소형기관차와 두번째 객차에 대한 최대 승객 수는 75명 입니다. 따라서 75 + 60 = 135입니다. 그러나 해당 객차를 선택하지 않는 경우, 바로 이전 객차에 대한 최대 승객수는 0명입니다. 0보다 135가 크므로 DP[2][4] = 135가 됩니다.

다섯번째 객차에 대해 생각해봅시다. 해당 객차를 선택하는 경우, 최대로 끌 수 있는 승객의 수는 10 + 30 = 40명 입니다. 첫번째 소형기관차를 제외한 나머지소형기관차와 세번째 객차에 대한 최대 승객수는 90명입니다. 따라서 90 + 40 = 130입니다. 그러나 해당 객차를 선택하지 않는 경우, 바로 이전 객차에 대한 최대 승객수는 135입니다. 130보다 135가 크므로 DP[2][5] = 135가 됩니다.

 

이렇게 표를 채워나가다 보면, 공통된 패턴을 알아차릴 수 있습니다. 해당 패턴, 즉 점화식은 DP[r][c] = max(DP[r - 1][c - maxCoachNumber] + sum(c - maxCoachNumber + 1, c) , DP[r][c - 1])로 표현할 수 있습니다.

 

 

풀이 코드 (JAVA)

DLS

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.stream.Stream;

public class Main {
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    private static int totalCoachNumber = 0;
    private static int[] passengers = null;
    private static int maxCoachNumber = 0;

    private static int maxPassenger = 0;
    
    private static void getMaxPassengerNumber() {
        dfs(0, 0, 0, true, 0);
        dfs(0, 0, 0, false, 0);
    }

    private static void dfs(int index, int smallTrainNumber, int selectedCoachNumber, boolean isSelected, int passengerNumber) {
        // 모든 객차를 탐색한 경우
        if (index >= totalCoachNumber) return;
        // 해당 객차를 선택한 경우
        if (isSelected) {
            // 선택한 객차 수가 최대 객차 수를 넘는 경우, 0으로 초기화해준다
            if (selectedCoachNumber >= maxCoachNumber) selectedCoachNumber = 0;
            // 새로 객차를 선택하는 경우, 새 소형 기관차를 준비한다
            if (selectedCoachNumber == 0) smallTrainNumber++;
            // 소형기관차가 4개 이상인 경우
            if (smallTrainNumber >= 4) return;
            // 선택된 객차 수를 증가시킨다
            selectedCoachNumber++;

            // 총 승객 수를 누적한다
            passengerNumber += passengers[index];
            // 최대 승객 수를 갱신한다
            maxPassenger = Math.max(passengerNumber, maxPassenger);
        }
        // 해당 객차를 선택하지 않은 경우, 소형 기관차의 객차가 끊기므로 초기화해준다
        else selectedCoachNumber = 0;

        // 재귀
        dfs(index + 1, smallTrainNumber, selectedCoachNumber, true, passengerNumber);
        dfs(index + 1, smallTrainNumber, selectedCoachNumber, false, passengerNumber);
    }
    
    public static void main(String[] args) throws IOException {
        try {
            totalCoachNumber = Integer.parseInt(br.readLine(), 10);
            passengers = Stream.of(br.readLine().split(" ")).mapToInt(passenger -> Integer.parseInt(passenger, 10)).toArray();
            maxCoachNumber = Integer.parseInt(br.readLine(), 10);

            getMaxPassengerNumber();
            System.out.println(maxPassenger);
        } catch (Exception e) {
        }
    }
}

DLS의 경우에 문제 풀이는 쉽습니다. 각 객차를 선택하거나 선택하지 않으므로써 모든 객차에 대해 검사를 하며, 최대 승객 수를 갱신합니다.

해당 문제에서 주의해야 할 부분은, 소형기관차는 연속된 객차를 운송할 수 있습니다. 즉, 특정 객차를 선택하지 않거나 운송할 수 있는 객차수를 초과한다면 반드시 다음 소형기관차를 준비해야된다는 것입니다.

DLS 특성상 최대한 깊게 탐색해야 하므로, 성능은 좋지 않습니다. 저도 제출해보니 시간초과가 뜨네요..

 

DP

(추후 업데이트 예정)