백준 13201번: 즉흥 여행 [C++]

작성일 | In
플래티넘 IV 플래티넘 IV

문제

즉흥 여행

풀이

$DP[d][i]$를 여행의 $d$번째 날에 $i$번째 지역에 도착하는 경로의 확률 중 가장 큰 것이라 정의합시다. $i$번째 공항에서 나가는 항공편의 개수의 합을 $T_i$라 하면 아래 점화식을 이용해 $DP$값을 모두 구할 수 있습니다.

\[DP[d + 1][j] = \max\left(DP[d][i] \times \frac{S_{ij}}{T_i}\right)\]

확률의 로그값을 저장하여 덧셈과 뺄셈 연산만으로 확률을 구하도록 하거나 long double등의 정밀도가 높은 자료형을 사용해야 맞을 수 있습니다.

시간 제한이 빡빡하므로 로그를 사용하지 않는 풀이에서는 $S_{ij} \div T_i$를 미리 구해놓고 재사용해야 시간 초과를 피할 수 있습니다.

테스트 케이스마다 시간 복잡도는 $\mathcal{O}(KN^2)$입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <bits/stdc++.h>
using namespace std;

using ldouble = long double;

ldouble maxProb[1111][111], prob[111][111];

int S[111][111];
string IATA[111];

void solve() {
    int N, K;
    cin >> N >> K;

    fill(&maxProb[0][0], &maxProb[K][N + 1], -1e18);

    for (int i = 1; i <= N; i++) {
        cin >> IATA[i];
        if (IATA[i] == "ICN")
            maxProb[0][i] = 1;
    }

    for (int i = 1; i <= N; i++) {
        int total = 0;

        for (int j = 1; j <= N; j++) {
            cin >> S[i][j];
            total += S[i][j];
        }

        for (int j = 1; j <= N; j++)
            prob[i][j] = (ldouble)S[i][j] / total;
    }

    for (int day = 0; day < K; day++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                maxProb[day + 1][j] =
                    max(maxProb[day + 1][j], maxProb[day][i] * prob[i][j]);
            }
        }
    }

    int ans = 1;
    for (int i = 2; i <= N; i++)
        if (maxProb[K][i] > maxProb[K][ans])
            ans = i;

    cout << IATA[ans] << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    return 0;
}

백준 13201번: 즉흥 여행 [C++]