여태 실버문제는 풀지 않았지만 코테문제는 실버에서 골드 수준으로 나온다는 걸 알게 되고 앞으로는 적극 실버를 풀 생각이다.
마침 대학교 알고리즘 시간에 분할정복, DP의 차이점과 상황에 따른 우수성을 배운지 얼마 지나지 않았어서 해당 문제를 보고 바로 DP로 풀어야 한다는 생각이 났다. 감사합니다 프로페서 조.
https://www.acmicpc.net/problem/9184
9184번: 신나는 함수 실행
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.
www.acmicpc.net
해당 문제는 이미 재귀 분할정복으로 구현되어 있는 식을 DP로 바꾸는게 풀이였다. 해당 식이 분할정복으로 나누었음에도 오히려 계산 식이 더 늘어나기 때문에 시간복잡도 측면에서 DP로 메모이제이션 하면서 푸는 게 훨씬 이득이다.
어차피 0 이하는 1이고, 20 이상은 DP[20][20][20] 이기 때문에 한 번만 3중 for문을 통해 DP 테이블을 구성하고 해당 테이블에서 계속 값을 얻으면 된다.
'알고리즘 문제 > 다이나믹 프로그래밍' 카테고리의 다른 글
| [Java] 다이나믹 프로그래밍 (동전 1) (0) | 2023.06.28 |
|---|---|
| [Java] 다이나믹 프로그래밍 (쉬운 계단 수) (0) | 2023.06.28 |
| [Java] 다이나믹 프로그래밍 (1,2,3 더하기 4) (0) | 2023.02.19 |
| [Java] 다이나믹 프로그래밍 (진우의 달 여행 (Large)) (0) | 2023.02.16 |
| [Java] 다이나믹 프로그래밍 누적 합 (구간 합 구하기5) (0) | 2023.02.01 |