티스토리 뷰
링크 : https://csacademy.com/contest/archive/task/amusement-park/
문제 요약
T개의 티켓을 가지고 1번 놀이공원부터 A번 놀이공원까지 순서대로 사용한다. 이 때, 내가 현재 갖고 있는 티켓 개수 T와 현재 놀이공원의 번호 A에 따라 리더기가 잘못 동작할 확률 P가 테이블로 주어진다. 이 P만큼의 확률로 리더기가 잘못 작동하면 티켓을 사용하지 않고 해당 놀이기구를 탈 수 있다. 남은 티켓이 0개가 될 때까지 반복해서 1번부터 A번까지 놀이기구 사용, A번까지 사용 후 다시 1번 놀이기구로 돌아오는 걸 반복할 때 갖고 있는 티켓 T개로 사용가능한 놀이기구 개수의 기댓값을 구하는게 문제.
T와 A는 모두 1000이하의 자연수.
풀이
기댓값 DP 문제인데 싸이클을 처리하는 방법이 굉장히 독특하다. 이걸 생각을 못해서 결국 답지를 봤기 때문에 풀이를 정리해 둠.
부분 문제의 해결 순서 간에 싸이클이 존재하는 경우 당연히 일반적인 방식의 DP로는 해결이 불가능하다. 여태껏 접했던 이런 싸이클이 있는 부류의 문제들은 전부 극한 개념을 이용해서 적절히 싸이클을 해소해주는 방식의 문제였는데 이 문제는 극한을 이용해서는 잘 풀리지 않는다.
이 풀이에서는 답 테이블 sol[i][j] = 티켓 i개 가지고 j번 놀이공원에서 시작했을 때 놀이공원 사용 개수의 기댓값으로 정의하고 문제를 푼다. 이렇게 정의하면 답은 당연히 sol[T][1]이 된다. base case는 티켓이 0개 있는 경우인데 이 경우는 티켓이 0개면 더 이상 놀이기구를 이용하지 않으므로 기댓값은 0이 된다. 즉 sol[0][1] ... sol[0][A] 는 모두 0이다.
이제 다른 경우에 대해 문제를 풀어야 하는데, sol[i][j] 리더기가 오작동 하는 경우의 기댓값은 P * sol[i][(j+1) % a] 이고, 정상 작동하는 경우는 P * sol[i-1][(j+1)%a] 이다. 여기서 문제는 리더기가 오작동하는 경우의 처리 때문에 같은 i값에 대해 싸이클로 서로가 서로를 참조하게 되어버린다는 것이다. 이걸 해결하기 위해서, X = sol[i][0] 으로 정의하고 모든 i라인의 sol 테이블값을 X에 관한 일차식으로 표현한다.
즉, sol[i][j] = a * sol[i][0] + b 꼴의 일차 방정식으로 표현한 다음, 먼저 각 테이블의 a,b 계수를 계산하고 sol[i][0] = a * sol[i][0] + b 로부터 sol[i][0]의 값을 구한 뒤 연쇄적으로 해당 값을 적용시켜서 i라인의 전체 기댓값을 구하는 과정을 반복해준다. 최종 시간복잡도는 O(N^2).
싸이클이 있을 때 그 싸이클을 이루는 요소중 하나의 결과값을 X로 정의한 뒤 나머지 싸이클 요소들을 X에 관한 식으로 표현하고, 그 식으로부터 X값을 구해서 연쇄적으로 적용시킨다. 라는게 핵심 아이디어. 이런 방식으로 DP에서 싸이클을 해소할 수 있다는게 굉장히 재밌었다.