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

다이나믹 프로그래밍 문제.

 

처음 이문제를 봤을 때

처음 시도했을 때의 코드 전문.

처음에 백트래킹으로 시도했다가 시간초과가 너무 많이났다.

(생각해보면 계단 개수가 최대 300개 인데,

이를 고려하면 경우의 수가 2의 지수승이 어마어마하게 크기 때문에 잘못된 접근이다.)

사실 시간초과 부분에 관련해서 게시물을 찾다가 반복문으로 충분히 해결가능 하다는 답변을 보았고,

얼핏 스쳐가는 코드에서 max 메서드를 보았다.

max 메서드는 오래동안 안 써왔어서 생각을 못했는데, max 메서드를 써서 접근하기로 했다.

따라서 이건 포기하고 다이나믹 프로그래밍의 Bottom Up 방식으로 접근하기로 했다.

 

다시 접근할 때

max 메서드를 오랜만에 써서 그런지 머리가 잘 안돌아갔다.

• max(A, B)는 A와 B중 큰 값을 return해주는 algorithm STL에 있는 메서드이다.

점화식을 찾으려 했는데 정말 어려웠다. DP의 Bottom Up 문제는 정말 잘못 짚으면 계속 어려운 것 같다.

그러던 중 처음부터 차근차근 보았는데, 다음과 같은 규칙을 발견했다.

• 지금 구하는 곳에서 2계단 전에서 오는 경우라면, 2계단 전 계단의 최대값(저장시켜놓은 최대값)을 그냥 사용하면 된다.
• 만일 지금 구하는 곳 바로 전 계단에서 오는 경우라면, 전 계단은 2계단 전에서 온 경우여야만 한다.

따라서 점화식을 써보면 A가 최대값을 저장하는 식이고, B가 해당 계단의 점수라고 할 때

An = max( A(n-2) + Bn, A(n-3) + B(n-1) + Bn )이 된다.

2계단 전에서 오는 경우와, 2계단 전에서 온 전 계단에서 오는 경우 어느 곳에서 더 큰지 비교하면 된다.

 

문제풀이

 

코드 전문

코드가 길지는 않다.

변수를 살펴보자면 계단의 개수를 나타내는 변수 floor_cnt,

각 계단의 점수를 저장하는 배열 floor_score,

각 계단에서 얻을 수 있는 최대 점수를 저장하는 배열 dp를 선언했다.

 

그리고 계단의 개수와 각 계단의 점수를 입력받는다.

dp배열에서 첫번째와 두번째는 이미 확정이 되기 때문에 미리 지정해준다.

그리고 위 점화식에 적어놓은 것처럼 비교를 해서 각 계단에서 얻을 수 있는 최대 점수를 저장해놓는다.

 

다이나믹 프로그래밍에서는 점화식을 잘 짜야할 뿐만 아니라,

이러한 최대값을 어떤식으로 update시킬지도 잘 생각해야 하는 것 같다.

오히려 이런 점에서는 다이나믹 프로그래밍이 다른 다익스트라, dfs, bfs 알고리즘보다 어려울 때도 있는 것 같다.

이런 문제는 오랜만에 접해서 그런지 생각하는게 쉽지 않았지만 많은 도움이 됐다.

 

GitHub - kimyunseok/study-record: my study-record

코드는 위에서 확인 가능하다.