[C++]백준 2579번: 계단 오르기

문제

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

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]) 이라고 할 수 있다.

코드1(max 함수와 getH 함수)

코드2(main 함수)

다이나믹 프로그래밍(DP)를 이용하여 다음과 같이 구현했더니 시간초과가 나오지 않고 문제 풀이에 성공했다.