목록기대값 dp (1)
블로그 옮겼습니다
Topcoder SRM 513 Div2(Medium) PerfectMemory
https://community.topcoder.com/stat?c=problem_statement&pm=11500 우선 문제는 흔히 알고있는 '사천성' 이라는 게임을 최소한의 턴 수로 클리어 하기 위해 필요한 턴 수의 기대값이다.그냥 그때 그때 최적의 선택을 할 때 클리어 하는 데 필요한 턴 수의 기대값이라고 생각하면 될 것 같다. 처음에 실수할 수 있는 것이 뭐냐면.. 실제로 게임을 할 때 뒤집혀 있는 두개의 칸을 선택하면 이 두개가 동시에 뒤집히는것이 아니라 하나씩 선택을 하는데, 하나를 선택하면 이것이 뒤집하고 이 정보를 바탕으로 더 최적의 선택을 할 수가 있기 때문에 답이 다르게 나온다는 사실이다. 문제에서 플레이어는 한번 뒤집었던 칸의 모양은 평생 기억한다고 되어있기 때문에 클리어 까지 필요한..
Algorithm/Problem Solving
2017. 4. 2. 10:40