[동적 계획법][시도X] GENIUS 지니어스

1. 완전 탐색

 

이 문제는 다음으로 재생될 곡은 바로 이전 곡에만 영향 받기때문에

마르코프 모델이라고 할 수 있다.

 

이 문제는 주어진 k분 30초에 좋아하는 노래들이 각각 나올 확률을 구하는 문제이다.

 

좋아하는 곡들의 번호들과 

i다음으로 j가 재생될 확률을 담고있는 행렬 T가 주어지고

각 곡의 길이가 주어진다

 

number 음악이 min분에 재생될 확률을 구하려면

일단 0 ~min 에 number 음악이 시작되는 확률을 먼저 구해야한다.

 

해당 음악이 min분에 재생될 확률은 

해당 음악이 min - number.len + 1에서부터 min까지 시작되는 확률을 전부 더한것과

같기때문이다. 

 

play(min, number) = min에서 number가 재생될 확률

 

play(min, number) = Σ ( play ( min - before.len , before) * T(before, number) )

 

playing(min, number) = min에서 number가 재생되고 있을 확률

 

playing(min, number) = Σ (play( i , number))      ( min - number.len < i <= min)

 

이 식들은 재귀함수로 쉽게 구현할 수 있다.

 

2. 반복적 동적 계획법

 

하지만 min의 최대값은 1,000,000 이므로 메모리가 많이 필요하다.

메모이제이션 하기에도 적당한 숫자가 아니다.

하지만 이를 반복적 동적 계획법을 이용하면 공간복잡도를 줄일 수 있다.

 

playing(min, number)에서 결국 number가 재생될 구간은 다음과 같다

 

min - number.len < <= min

 

min 을 포함하여 최대 4개의 시작점만 알면 된다는 것이다.

 

play(min, number) 에서도 마찬가지이다. 

각 곡의 길이는 4분 이하 이므로

 

min : 다음 4경우를 더한 값이다.

min - 4: 4분 짜리 곡들이 끝나고 number가 시작되는 경우

min - 3: 3분 짜리 곡들이 끝나고 number가 시작되는 경우

min - 2: 2분 짜리 곡들이 끝나고 number가 시작되는 경우

min - 1: 1분 짜리 곡들이 끝나고 number가 시작되는 경우

 

여기서도 4개의 정보만 필요하다.

 

그러므로 이 문제에서는 min * n 개를 저장해야하는게 아니라

5 * n개를 저장하면 된다는 것이다. (여유공간 + 1) 

 

k를 0 부터 k 까지

차례대로 업데이트 할 시 이

전 정보가 필요없어지기 때문이다.

 

그러므로 

슬라이딩 윈도 기법을 사용할 수 있다.

 

3. 거듭 제곱 동적 계획법

 

 

GENIUS