[BOJ 23815] 백준 23815번 - 똥게임
1. 문제
$23815$. 똥게임 (2021 POSTECH Programming Open Contest C번)
2. 풀이
여러 가지 선택지 중 하나를 선택해가며 최적의 결과값을 찾는 문제라서 다이나믹 프로그래밍(DP)으로 푼다.
할 수 있는 행동은 세 가지가 있다.
- 첫 번째 선택지를 선택하는 경우
- 두 번째 선택지를 선택하는 경우
- 선택지를 건너뛰는 경우
선택지를 건너뛰게 되면, 선택지를 건너뛰지 않은 값과 선택지를 한번 건너뛴 값들이 구분이 되어야 한다. 그래야 선택지를 이미 한번 건너뛴 값들이 다시는 선택지를 건너뛰지 못한다.
첫 번째 선택지를 선택하는 경우와 두 번째 선택지를 선택하는 경우는 구분해도 상관은 없지만, 둘 다 선택지를 건너뛰지 않는 경우이므로 바로 maximum을 구해서 하나의 케이스로 통합할 수도 있다.
$dp[i][0] \rightarrow$ $i$번째까지 선택하며 선택지를 건너뛴 적 없는 최댓값 (코드 51줄)
이전까지 선택지를 건너뛰지 않았어야 하기 때문에 $dp[i-1][0]$에서 첫 번째 선택지를 선택한 경우와 두 번째 선택지를 선택한 경우 중 최댓값을 구한다.
$dp[i][1] \rightarrow$ $i$번째까지 선택하며 선택지를 한번 건너뛴 최댓값 (코드 52줄)
$i-1$번째까지는 건너뛰지 않았다가 $i$번째에서 건너뛰는 경우($dp[i-1][0]$), $i-1$번째 기준 이미 한 번 건너뛴 경우($dp[i-1][1]$)에서 첫 번째 선택지를 선택한 경우와 두 번째 선택지를 선택한 경우 (총 세 가지) 중 최댓값을 구한다.
계산할 때, $0$ 이하의 값은 게임 오버이므로 $0$으로 통일하여 처리한다. (코드 30줄)
3. 채점 결과
4. 회고
dp 계산에 들어가는 값을 잘못 정리해서, 게임 오버 $0$ 처리를 잘못해서 WA를 받았다.
댓글남기기