[알고스팟] 지니어스

문제 링크

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • GENIUS
  • 20000ms
  • 65536kb
  • 751
  • 177 (23%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

MP3 플레이어에 들어 있는 곡들을 전부 셔플 모드로 들을 때 최대의 문제점은 서로 어울리지 않는 노래들이 갑자기 나올 수 있다는 것입니다. 끈적한 애시드 재즈를 듣고 있다가 갑자기 시끄러운 데스 메탈이 나오는 것만큼 분위기를 깨는 것도 없지요. 때문에 전세계에서 가장 잘 나가는 MP3 플레이어를 생산하는 오렌지 사에서는 이번에 지니어스라는 기능을 출시했습니다. 지니어스는 MP3 플레이어에 들어 있는 곡들을 셔플 모드로 들을 때 잘 어울리는 것끼리 순서대로 재생되도록 해 줍니다.

태윤이는 오렌지 사의 새 MP3 플레이어를 산 뒤 재미로 지니어스의 동작 원리를 분석해 보았습니다. 지니어스를 사용하면 한 곡 다음에 다음 곡이 재생될 확률은 두 곡의 유사도에 따라 결정됩니다. 태윤이는 MP3 플레이어에 담긴 음악들 간의 유사도를 조사해, i 번 곡 다음에 j 번 곡이 재생될 확률을 나타내는 확률 행렬 T 를 만들었습니다.

태윤이는 방금 재생 버튼을 눌러 0번 곡을 듣기 시작했습니다. K 분 30초가 지난 후 태윤이가 좋아하는 곡이 재생되고 있을 확률은 얼마일까요? MP3 플레이어에 들어 있는 곡들의 길이는 모두 1분, 2분, 3분 혹은 4분입니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 50) 가 주어집니다. 각 테스트 케이스의 첫 줄에는 MP3 플레이어에 들어 있는 곡의 수 N (1 <= N <= 50 ) 과 K (1 <= K <= 1,000,000) , 그리고 태윤이가 좋아하는 곡의 수 M (1 <= M <= 10) 이 주어집니다. 그 다음 줄에는 N 개의 정수로 각 곡의 길이 Li 가 분 단위로 주어지고, 그 후 N 줄에는 한 곡이 재생된 후 다음 곡이 재생될 확률을 나타내는 행렬 T 가 주어집니다. T 의 i 번 줄의 j 번 숫자 (0 <= i,j < N) T[i,j] 는 i 번 곡이 끝난 뒤 j 번 곡을 재생할 확률을 나타냅니다. T 의 각 행의 합은 1 입니다. 각 테스트 케이스의 마지막 줄에는 M 개의 정수로 태윤이가 좋아하는 곡의 번호 Qi 가 주어집니다.

출력

각 테스트 케이스마다 한 줄로 태윤이가 좋아하는 M 개의 곡에 대해 각 곡이 재생되고 있을 확률을 출력합니다. 10^-7 이하의 절대/상대 오차가 있는 답은 정답으로 인정됩니다.

예제 입력

3
3 6 3
4 4 2
0.18 0.40 0.42
0.15 0.46 0.39
0.58 0.23 0.19
0 1 2
4 10 4
1 3 2 4
0.26 0.07 0.49 0.18
0.21 0.33 0.15 0.31
0.41 0.20 0.38 0.01
0.28 0.31 0.18 0.23
2 0 3 1
4 1000 4
4 3 4 4
0.08 0.47 0.12 0.33
0.10 0.02 0.39 0.49
0.08 0.33 0.35 0.24
0.14 0.19 0.58 0.09
1 3 2 0 

예제 출력

0.42360000 0.49660000 0.07980000 
0.31060929 0.13791635 0.26756048 0.28391388 
0.18648004 0.28409359 0.42243515 0.10699122 

어떻게 풀까?

이 문제를 단순히 반복적 동적 계획법을 이용해서 풀었더니 시간 초과가 나버립니다.

다른 유용한 테크닉을 사용해야하죠!

우선! 이 문제에서 영향을 줄 수 있는 부분을 찾아야 합니다!

노래의 길이는 총 4분 입니다! 

그러면, 방금 시작한 노래, 1분 전에 시작한 노래, 2분 시작한 끝난 노래, 3분 전에 시작한 노래가 영향을 줄 수 있겠죠!

4분 전에 시작한 노래는 노래가 끝난 후 다른 노래가 이어지겠죠. 노래를 확인하는게 30초 뒤이기 때문입니다!

이는 결국 '1분 전 시작한 노래'로 넣어야 하는 것입니다.

테스트 케이스에서 가장 긴 노래의 길이를 찾았고, 그 길이가 l이라고 한다면, 방금 시작한 노래, 1분 전에 시작한 노래, ... l-1 분 전에 시작한 노래가 영향을 줄 것 입니다.

또한, 노래의 종류가 n개이기 때문에 각 시작된 노래마다 l 개의 노래가 존재하겠죠!

이를 C(i)라고 합시다!

그렇다면 C(i+1)은 어떻게 구성될까요?

3분 전 시작한 노래는 4분 전 시작한 노래가 되기 때문에 사라져 버릴 것입니다.

2분 전 시작한 노래는 3분 전 시작한 노래가 되고,

1분 전 시작한 노래는 2분 전 시작한 노래가 되겠죠!

그렇다면 가장 중요한 재생 중인 노래는 어떻게 될까요!?

3분 전 시작한 노래를 생각해봅시다.

3분 전에 시작한 노래는 노래 길이가 4일 경우에! 방금 시작한 노래가 될 수 있습니다.

2분 전에 시작한 노래는 

노래 길이가 3일 경우에 방금 시작한 노래가 되겠죠! 4 일 경우에는 나중에 시작할 노래가 될 것입니다.

이러한 정보들을 이용하면 방금 시작한 노래 i를 구할 수 있습니다!

i번 전의 노래가 j라고 하고, j번 노래의 길이가 len[j]라고 합시다.

또한, j번 노래 다음에 i번 노래가 나올 확률을 p[j][i]라고 한다면,

노래 i가 방금 시작할 확률은 노래 j가 끝난 다음에 노래 i가 틀어져야한다는 것과 같은 의미이죠!

따라서,

그러고 보니 처음에 저 (len[i]-1)분 전에 노래 j가 끝날 확률을 열 벡터 C에 넣어 놨었군요!

맨 위에 l-1분 전에 노래가 시작할 확률을 위에 먼저 놓았습니다. 그리고 방금 노래가 시작할 확률은 (l-1)*n 번째 행부터 시작하죠!

 

이를 이용하면 열 벡터 C를 이용해서 C(i)에서 C(i+1)로 가기 위한 가중치를 저장하는 행렬

즉, (l*n) x (l*n) 정사각행렬을 만들 수 있습니다!

이 행렬을 W라고 합시다.

그럼, W에서 위의 (l-1)*n 행 까지는 이전에 시작했던 노래들보다 1 분 늦게 시작한 노래들을 그대로 가져오면 됩니다!

 
    for (int i = 0, imax = (maxLen -1) * n; i < imax; i++) {
        W[i][i + n] = 1;
    }

 

그리고 (l-1)*n 행부터는 위에서 이용했던 공식을 이용하여서 만들 수 있죠!

합치면 아래와 같은 모습이 됩니다.

void initW() {
    memset(W, 0, sizeof(W));
 
    for (int i = 0, imax = (maxLen -1) * n; i < imax; i++) {
        W[i][i + n] = 1;
    }
 
    //슬라이딩 윈도우 행렬
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            W[(maxLen - 1)*n + i][(maxLen - len[j]) * n + j] = p[j][i];
        }
    }
}

이제 이렇게 W를 구하면, C(0)를 알고 있기 때문에 C(i)를 구하는 식을 만들 수 있죠!

또한, C(0)에서 0번 곡만 재생되고 있고, 이 0번 곡의 위치가 C[(l-1)*n]이기 때문에 행렬의 제곱을 계산하고 난 다음에 원하는 i번째 답을 뽑고 싶다면, W[i][(l-1)*n] 값만 보면 됩니다!

마지막으로... 만약 노래 j의 길이가 4라면, 방금 전에 시작한 j 노래 뿐만 아니라, 3분 전에 시작한 j 노래와 2분 전에 시작한 j 노래, 1분 전에 시작한 j 노래 모두 i에 대한 답이 될 수 있다는 것을 명심하면 됩니다!

코드

#include<cstdio>
#include<cstring>
 
double p[50][50] = { 0 };
int len[50], num[10],n, maxLen;
double res[50];
double W[200][200], tw[200][200]; //W : 슬라이딩 윈도우
double cw[200][200];
 
void initW() {
    memset(W, 0, sizeof(W));
 
    for (int i = 0, imax = (maxLen -1) * n; i < imax; i++) {
        W[i][i + n] = 1;
    }
 
    //슬라이딩 윈도우 행렬
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            W[(maxLen - 1)*n + i][(maxLen - len[j]) * n + j] = p[j][i];
        }
    }
}
 
void mul(double W1[200][200], double W2[200][200]) {
    double result[200][200] = { 0 };
    
    for (int i = 0, imax = maxLen * n; i < imax; i++) {
        for (int j = 0, jm = maxLen * n; j < jm; j++) {
            result[i][j] = 0;
 
            for (int k = 0, km = maxLen * n; k < km; k++) {
                result[i][j] += W1[i][k] * W2[k][j];
            }
        }
    }
 
    memcpy(W1, result, sizeof(result));
}
 
void pow(int n) {
    if (n == 0) {
        return;
    }
 
    if (n == 1) {
        memcpy(tw, W, sizeof(W));
        return;
    }
 
    pow(n / 2);
    memcpy(cw, W, sizeof(W));
    
    mul(W, cw);
    if (n & 1) {
        mul(W, tw);
    }
}
 
int max(int i1, int i2) {
    return i1 > i2 ? i1 : i2;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
    
    while (t--) {
        int k, m;
 
        maxLen = 0;
        scanf("%d %d %d\n", &n, &k, &m);
 
        for (int i = 0; i < n; i++) {
            scanf("%d \n", &len[i]);
            res[i] = 0;
            maxLen = max(maxLen, len[i]);
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%lf \n", &p[i][j]);
            }
        }
        for (int i = 0; i < m; i++) {
            scanf("%d \n", &num[i]);
        }
 
        initW();
        pow(k);
 
        for (int i = 0; i < m; i++) {
            int ri = num[i];
 
            //노래 길이 len[num[i]] 이후에 시작한 i 노래들은 모두 영향을 줄 수 있는 노래들이다!
            for (int st = 0; st < len[num[i]]; st++) {
                res[i] += W[(maxLen - st - 1)*n + ri][(maxLen - 1)*n];
            }
        }
 
        for (int i = 0; i < m; i++) printf("%.8lf ", res[i]);
        printf("\n");
    }
 
    return 0;
}

여담

완전히 정말로 어려웠습니다...

행렬로 계산하는건 처음 해봤네요!

대신에 정말 많은 것을 알아낸 것 같습니다!

뭐랄까.. 예전엔 못풀던 문제들도 이제는 풀 수 있을 것 같은 자신감을 얻었습니다.

저도 이 문제 결국 게속 생각해보다가 못풀어서 답지를 봤습니다 ㅎㅎ

이 문제는 노래의 길이가 l, 노래의 종류가 n, 시간이 k라고 한다면,

l*n차 정사각행렬이 됩니다. 따라서 시간복잡도는 가 됩니다!