algospot 지니어스 (문제 ID: GENIUS)

알고스팟 문제 링크: https://www.algospot.com/judge/problem/read/GENIUS

algospot.com :: GENIUS

MP3에 들어있는 노래수와 노래들의 재생시간, 선호하는 노래, 특정 노래후에 다음노래가 나올확률(2차원 배열)등이 주어졌을때 K분30초 후에 선호하는 노래가 나오고 있을 확률을 구하는 문제이다.

일단 K의 범위가 [1, 1000000]이기 때문에 cache공간 문제 때문에 재귀적이 DP로는 해결할수 없을것 같았고, 평범한 반복적DP도 시간복잡도 문제때문에 사용하기 힘들어 보였다.

해답으로는 행렬 거듭제곱을 이용한 동적 계획법이 있었다.

start(time, song) = 재생을 시작한지 time분 후에 song번 노래가 재생을 시작할 확률이라하자

start(time-3)부터 start(time)까지를 포함하는 크기 4*N의 열벡터 C(time)를 정의하고 C(time+1)=W*C(time)인 W를 구하여 k만큼 거듭제곱한 후 C(0)와 곱해주면 원하는 답을 얻을수 있다.

하지만 이러한 행렬들을 관리하기 위해서는 여러가지 메서드들을 직접 정의하고 연산자들도 오버로딩 해줘야 했기 때문에 무척 까다로운 문제였다. 또한 k의 범위가 무척 크기 때문에 거듭제곱의 횟수또한 줄이기 위해 분할정복을 사용하였다.

 

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/9.%20DP-Technic/GENIUS.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략1