[파이썬] 백준 28017번 - 게임을 클리어하자 풀이

https://www.acmicpc.net/problem/28017

티어: 골드 5

 

로직

딱봐도 DP 쓸거같이 생긴 문제입니다.

 

1. 각 회차, 무기별 클리어 시간을 times 2차원 배열에 저장합니다. - times[회차][무기]

2. times와 동일한 크기의 dp 배열을 생성하고, dp 배열의 첫번째 인덱스는 첫 회차이므로 times[0]과 동일하게 설정해줍니다.

3. n번째 회차에서 m번째 무기를 썼을 때의 dp값은 dp[n][m] = times[n][m] + min(dp[n-1][0], min[n-1][1], ... ) 으로 표현할 수 있습니다. 이 때 이전 회차에 썼던 무기를 연달아 쓸 수 없으므로 dp[n-1]의 최솟값을 구할 때 dp[n-1][m]을 제외한 최솟값을 구해야 합니다.

4. 1부터 N-1까지 dp[i][j]의 값을 모두 구해줍니다.

 

마지막 회차까지 각 무기별로 클리어했을 때의 최솟값은 dp[-1]입니다. 이중 가장 작은 값인 min(dp[-1])가 문제의 답이 됩니다.