티스토리 뷰

문제 풀이

[BOJ 2057] 계단 오르기

RiKang 2017. 10. 31. 17:15
반응형

일단 마지막 계단까지 올라가는 최댓값을 구해야 하고 계단은 한번에 1개 혹은 2개를 올라갈 수 있으니 아래와 같이 설정해 볼 수 있다.


DP( i ) = i번째 계단까지 올라가는 최댓값

하위 문제 : DP( i-1 ), DP( i-2 )


이 때, 아래에 있는 계단으로 갈 수가 없으니 사이클이 생길 일에 대해선 걱정할 것이 없다.


하지만 ‘연속된 세 개의 계단을 모두 밟아서는 안 된다. ’는 조건이 있는데 이를 DP( i-1 ), DP( i-2 )의 정보만 가지고는 처리를 할 수 없으므로 DP 설정에 정보를 추가해야 한다.


DP( i, j ) = 마지막 점프가 j 개를 올라가는 점프일 경우, i 번째 계단까지 올라가는 최댓값

하위 문제 : DP( i-1, 2 ), DP( i-2, 1 ), DP( i-2, 2 )

( DP( i-1, 1 ) 의 상태에서 i 번째 계단으로 가면 ‘연속된 세 개의 계단을 모두 밟아서는 안 된다. ' 조건에 위배되기 때문에 제외 )


이렇게 설정을 추가하면 하위 문제만 가지고 답을 구할 수 있게 되어 해결할 수 있다.


DP( i, 1 ) = DP( i-1, 2 ) + 계단 i의 점수

DP( i, 2 ) = max( DP( i-2, 1 ), DP( i-2, 2 ) ) + 계단 i의 점수



반복적 동적 계획법




재귀적 동적 계획법

반응형

'문제 풀이' 카테고리의 다른 글

[CF 371 D] Animals and Puzzle  (0) 2017.10.31
[BOJ 4008] 특공대  (0) 2017.10.31
[CF 146 B] Let's Play Osu!  (0) 2017.10.31
[BOJ 2533] 사회망 서비스  (0) 2017.10.31
[BOJ 5060] 무글 맵스  (0) 2017.10.31