221028 문제 풀이 기록
2022. 10. 28. 22:55
P3 | 5834 - Cow Run
풀이 시간: 42분
시도 횟수: 3회
체감 난이도: P3
풀이 쓸 의향: 下
풀이
더보기
dp[l][r][x][y] = dp[왼쪽에 남은 갯수][오른쪽에 남은 갯수][이전에 좌 골랐으면 0, 아니면 1][지금 좌 고르는거면 0, 아니면 1] 로 dp 계산하기 -> dp[l][r][x][y] = abs(현재위치 - 이전 위치) * (l+r) + min(dp[l-1][r][y][0], dp[l-1][r][y][0]) (x==0일때). 무조건 왼쪽에서 제일 가까운 소나 오른쪽에서 가장 가까운 소를 골라야 한다는 사실을 토대로 dp 계산.
여담: dp식 세우면서 pos의 유일성을 해치는 방식으로 짜서 -1, long long 안써서 -1
그보다 원래 DP 엄청 못했는데 이제 조금씩 감을 잡는 느낌... :)
'PS > 풀이 기록장' 카테고리의 다른 글
| 221117 문제 풀이 기록 (0) | 2022.11.17 |
|---|---|
| 221029 문제 풀이 기록 (0) | 2022.10.30 |
| 221027 문제 풀이 기록 (0) | 2022.10.27 |
| 221026 문제 풀이 기록 (0) | 2022.10.26 |
| 221025 문제 풀이 기록 (0) | 2022.10.25 |