BOJ 9023 - 연습시즌 링크
(2024.03.27 기준 G2)

문제

두 야구팀 $X$, $Y$의 훈련 일정이 주어진다. 각 훈련 일정은 $7$개의 도시 중 한 곳에서 훈련하게 되며, 주어지는 순서대로 방문해야 한다. 두 팀 $X$, $Y$가 연습 시즌을 시작하는 날과 마치는 날은 반드시 동일해야 하며, 연습 시즌 동안 각 팀은 방문해야 하는 도시를 방문하여 훈련을 하거나 호텔에서 휴식할 수 있다.

모든 도시의 야구장은 하루 사용할 때 $C$를 지불해야 한다. 만약 두 팀이 같은 도시를 방문해서 훈련할 경우, $C$를 분담해서 지불하면 되기 때문에 저렴해진다.

호텔에서 휴식할 경우, 연박 중 첫 날에만 독점사용비 $D$를 지불해야 하며, 사용하는 기간동안 하루당 $d$만큼의 비용을 추가로 지불해야 한다. 즉, 연속으로 $w$일 동안 휴식할 경우 $D + w \times d$만큼 지불해야 한다.

두 팀이 지출해야 하는 비용의 합의 최솟값 출력

알고리즘

DP

풀이

이 문제의 복병은 바로 호텔에서의 연박이다. 다른 말로는 $D$를 지불해야 하는 경우 때문에 스택, 그리디 같은 풀이가 먹히지 않을 것이다.

일단 두 팀의 일정을 진행할 수 있는 방법을 나열해보자.
1. 팀 $X$는 훈련, 팀 $Y$는 휴식
2. 팀 $X$는 휴식, 팀 $Y$는 훈련
3. 두 팀 다 훈련

두 팀 다 휴식하는 경우는 제외해야 한다. 휴식비만 더 늘고, 두 팀의 훈련 일정은 줄어들지 않고 그대로이기 때문에 절대 최적값이 될 수 없다.

세 번째 방법은 무조건 $C$ 아니면 $C \times 2$가 더해지기 때문에 신경 쓸 필요는 없어 보인다. 이제 첫, 두 번째 방법에서 휴식에 따른 지불하는 방법을 어떻게 해야 할지 생각해야 한다.
일단 $D$를 지불해야 하는 경우는 언제일까? 바로 전날에 호텔 사용 유무이다. 그러면 각 팀이 전날에 호텔을 사용했는지를 저장해놓으면 해결된다.

그럼 결국 아래와 같은 점화식을 세우면 문제를 해결할 수 있다.
$i$는 팀 $X$의 진행한 훈련 일정의 수, $xr$은 팀 $X$가 전날 호텔에서의 휴식 유무, $j$는 팀 $Y$의 진행한 훈련 일정의 수, $yr$은 팀 $Y$가 전날 호텔에서의 휴식 유무를 나타낼 때,
$dp(i,j,xr,yr) = \min(dp(i+1,j+1,0,0)+cost^{C \text{ if } X_i=Y_j}_{C \times 2 \text{ else}}, dp(i+1,j,0,1) + C + d + cost^{0 \text{ if } yr=1}_{D \text{ else}},dp(i,j+1,1,0) + C + d + cost^{0 \text{ if } xr=1}_{D \text{ else}})$

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAX = 100, inf = INT_MAX;

int C, D, d, X[MAX], Y[MAX], dp[MAX][MAX][2][2];

int dfs(int i, int j, int xr, int yr){
    if (!X[i] && !Y[j]) return 0; // 모든 훈련 일정이 끝났다면 0을 반환하고 끝낸다.

    // 현재 상태가 최적값이 저장된 상태이면 최적값을 반환하고 끝낸다.
    if (dp[i][j][xr][yr] > -1) return dp[i][j][xr][yr];

    dp[i][j][xr][yr] = inf;

    // 팀 X의 훈련 일정은 끝난 상태
    if (!X[i]){
        int cost = C + d; // 팀 Y의 야구장 사용 + 팀 X의 호텔 사용
        if (!xr) cost += D; // 팀 X의 호텔 사용 첫 날이라면 독점사용비 지불
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i, j + 1, 1, 0) + cost);
    }

    // 팀 Y의 훈련 일정은 끝난 상태
    else if (!Y[j]){
        int cost = C + d; // 팀 X의 야구장 사용 + 팀 Y의 호텔 사용
        if (!yr) cost += D; // 팀 Y의 호텔 사용 첫 날이라면 독점사용비 지불
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i + 1, j, 0, 1) + cost);
    }

    else{
        // 팀 X는 훈련, 팀 Y는 휴식
        int cost = C + d; // 팀 X의 야구장 사용 + 팀 Y의 호텔 사용
        if (!yr) cost += D; // 팀 Y의 호텔 사용 첫 날이라면 독점사용비 지불
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i + 1, j, 0, 1) + cost);

        // 팀 X는 휴식, 팀 Y는 훈련
        cost = C + d; // 팀 Y의 야구장 사용 + 팀 X의 호텔 사용
        if (!xr) cost += D; // 팀 X의 호텔 사용 첫 날이라면 독점사용비 지불
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i, j + 1, 1, 0) + cost);

        // 두 팀 다 훈련
        if (X[i] == Y[j]) cost = C; // 같은 도시인지 확인한다.
        else cost = C * 2;
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i + 1, j + 1, 0, 0) + cost);
    }

    return dp[i][j][xr][yr];
}

void solve(){
    cin >> C >> D >> d;
    for (int i = 0; ; i++){
        cin >> X[i];
        if (!X[i]) break;
    }
    for (int i = 0; ; i++){
        cin >> Y[i];
        if (!Y[i]) break;
    }

    // dp(i, j, xr, yr)
    // 현재 팀 X는 훈련 일정을 i번째까지 진행했고, 전날 호텔에서 휴식했는지와
    // 현재 팀 Y는 훈련 일정을 j번째까지 진행했고, 전날 호텔에서 휴식했는지를 나타내는 상태일 때
    // 앞으로 남은 훈련 일정들을 모두 진행했을 때의 최적값
    memset(dp, -1, sizeof(dp));
    cout << dfs(0, 0, 0, 0) << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int T; cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline
from math import inf

def dfs(i, j, xr, yr):
    if not X[i] and not Y[j]: # 모든 훈련 일정이 끝났다면 0을 반환하고 끝낸다.
        return 0

    if dp[i][j][xr][yr] > -1: # 현재 상태가 최적값이 저장된 상태이면 최적값을 반환하고 끝낸다.
        return dp[i][j][xr][yr]

    dp[i][j][xr][yr] = inf

    # 팀 X의 훈련 일정은 끝난 상태
    if not X[i]:
        cost = C + d # 팀 Y의 야구장 사용 + 팀 X의 호텔 사용
        if not xr: # 팀 X의 호텔 사용 첫 날이라면 독점사용비 지불
            cost += D
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i, j + 1, 1, 0) + cost)

    # 팀 Y의 훈련 일정은 끝난 상태
    elif not Y[j]:
        cost = C + d # 팀 X의 야구장 사용 + 팀 Y의 호텔 사용
        if not yr: # 팀 Y의 호텔 사용 첫 날이라면 독점사용비 지불
            cost += D
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i + 1, j, 0, 1) + cost)

    else:
        # 팀 X는 훈련, 팀 Y는 휴식
        cost = C + d # 팀 X의 야구장 사용 + 팀 Y의 호텔 사용
        if not yr: # 팀 Y의 호텔 사용 첫 날이라면 독점사용비 지불
            cost += D
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i + 1, j, 0, 1) + cost)

        # 팀 X는 휴식, 팀 Y는 훈련
        cost = C + d # 팀 Y의 야구장 사용 + 팀 X의 호텔 사용
        if not xr: # 팀 X의 호텔 사용 첫 날이라면 독점사용비 지불
            cost += D
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i, j + 1, 1, 0) + cost)

        # 두 팀 다 훈련
        if X[i] == Y[j]: # 같은 도시인지 확인한다.
            cost = C
        else:
            cost = C * 2
        dp[i][j][xr][yr] = min(dp[i][j][xr][yr], dfs(i + 1, j + 1, 0, 0) + cost)

    return dp[i][j][xr][yr]

for _ in range(int(input())):
    C, D, d = map(int, input().split())
    X = list(map(int, input().split()))
    Y = list(map(int, input().split()))

    # dp(i, j, xr, yr)
    # 현재 팀 X는 훈련 일정을 i번째까지 진행했고, 전날 호텔에서 휴식했는지와
    # 현재 팀 Y는 훈련 일정을 j번째까지 진행했고, 전날 호텔에서 휴식했는지를 나타내는 상태일 때
    # 앞으로 남은 훈련 일정들을 모두 진행했을 때의 최적값
    dp = [[[[-1] * 2 for _ in range(2)] for _ in range(100)] for _ in range(100)]
    print(dfs(0, 0, 0, 0))