GENIUS (중, p. 359)

문제#

어떻게 풀었나?#

처음에는 상태공간을 dp[노래 번호][분] = 노래 번호가 x분에 play중일 확률로 잡고 dp[0][L[0]-1]까지 1.0을 대입하여 초기화 한 뒤 반복문 DP로 답을 구하려고 했다. 하지만, 예시 출력 결과가 다른 것을 보고 뭔가 잘못됐다는 것을 깨달았다.

잘 생각해보니, 4분짜리 30번 곡을 play중이고 현재 1분정도 들었는데, 2분짜리 28번 곡을 play중일 확률은 0일 수밖에 없는데, 위의 방식대로라면 dp[28][3] = dp[30][1]*T[30][28] 로 답을 구하게 된다.

그래서 상태공간을 dp[노래 번호][분] = 노래 번호가 x분에 play가 끝날 확률로 잡았더니 AC를 받을 수 있었다.

정답 코드#

#include <bits/stdc++.h>
using namespace std;
int N, K, M;
int L[51];
double T[51][51];
int Q[51];
const int MASK = (1 << 4) - 1;
double dp[MASK + 1][51];
void Init() {
    for(int i = 0; i <= MASK; i++) {
        for(int j = 0; j <= 50; j++) {
            dp[i][j] = 0;
        }
    }
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int tc; cin >> tc;
    while(tc--) {
        cin >> N >> K >> M;
        for(int i = 0; i < N; i++) {
            cin >> L[i];
        }
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                cin >> T[i][j];
            }
        }
        for(int i = 0; i < M; i++) {
            cin >> Q[i];
        }

        Init();
        dp[L[0]][0] = 1.0;
        for(int s = L[0] + 1; s <= K + 4; s++) {
            for(int i = 0; i < N; i++) {
                if(s - L[i] < 0) continue;
                double& res = dp[s & MASK][i];
                res = 0;
                for(int j = 0; j < N; j++) {
                    // j->i
                    res += dp[(s - L[i]) & MASK][j] * T[j][i];
                }
            }
        }
        for(int i = 0; i < M; i++) {
            double sum = 0;
            for(int j = K + 1; j <= K + 4; j++) {
                if(j - L[Q[i]] <= K) {
                    if(dp[j & MASK][Q[i]]) {
                        sum += dp[j & MASK][Q[i]];
                    }
                }
            }
            printf("%.8lf ", sum);
        }
        puts("");
    }
    return 0;
}