문제
https://www.acmicpc.net/problem/2579
문제이해
계단의 개수와 각 계단의 점수를 입력으로 받고 정해진 규칙에 따라서 가장 점수를 많이 얻을 수 있는 방법을 구하여 출력한다.
문제해결
다이나믹 프로그래밍(DP)를 제대로 알지 못해서 재귀로 풀려고 시도를 했지만 시간초과가 나오게되었다.
다이나믹프로그래밍(DP)를 통해 풀어야 시간초과가 해결되다는 것을 재귀로 하고 나서야 깨달았다.
DP는 복잡한 문제의 큰 부분을 작은 부분으로 나누어 해결하여 이를 조합한 후 전체 문제의 해를 도출하는 알고리즘 설계 기법이다.
dp[x]는 x번째 계단까지의 점수의 최댓값을 의미한다.
st[x]는 x번째 계단의 점수를 의미한다.
그렇다면 dp[1] 은 당연히 st[1] 이라고 할 수 있다. dp[2] 또한 st[1] + st[2]라고 할 수 있다.
dp[3]을 구하려면 계단 3개를 오르는 방법들 중 최댓값을 구해야 한다.
계단 3개를 오르는 방법은 st[1] + st[3] 그리고 st[2] + st[3]이 있다. 두가지 중 큰 값을 return 하는 함수를 max라고 했을 때 dp[3] = max(st[1] + st[3], st[2] + st[3])라고 할 수 있다.
정리하자면
dp[1] = st[1]
dp[2] = st[1] + st[2]
dp[3] = max(st[1] + st[3], st[2] + st[3])
이다.
dp[N] (N > 3) 부터는 dp[N] = max(dp[N - 2] + st[N], dp[N - 3] + st[N - 1] + st[N]) 이라고 할 수 있다.
다이나믹 프로그래밍(DP)를 이용하여 다음과 같이 구현했더니 시간초과가 나오지 않고 문제 풀이에 성공했다.
'Coding' 카테고리의 다른 글
[C++]백준 1182번: 부분수열의 합 (0) | 2023.07.09 |
---|---|
[C++]백준 2644번: 촌수계산 (0) | 2023.07.08 |
[C++]백준 10816번: 숫자 카드 2 (0) | 2023.07.07 |
[C++]백준 14891번: 톱니바퀴 (0) | 2023.07.06 |
[C++]백준 2485번: 가로수 (0) | 2023.07.05 |