목록계단 오르기 (1)

-

DP :: 백준 :: 계단 오르기 :: 2579

계단오르기 2579https://www.acmicpc.net/problem/2579 [문제 풀이] i번째 계단을 밟았을 때 최댓값은 두 경우 - i-2번째 계단 밟고 i번째 밟을 경우 - i-1번째 계단 밟고 i번째 밟을 경우중 최댓값을 고르면 답!!??이 아니라 틀린다!! 2번조건 "연속된 세 개의 계단을 밟으면 안된다"는 조건이 있기 때문이다! 자, 그러면 어떻게 풀어야 할까?일단 2차원 배열을 생성한다. i번째 계단을 밟았을 때 1) 1번 연속으로 밟은 경우 : dp[1][i] 2) 2번 연속으로 밟은 경우 : dp[2][i]두 경우로 나눌 수 있다! 이때, 1) i번째 계단을 1번 연속으로 밟기 위해서는 i-2번째 계단에서 2칸 이동하는 방법밖에 없으므로 dp[1][i] = max(dp[1][i-..
알고리즘/DP 2016. 11. 2. 14:45
Prev 1 Next