[ 백준2579 - 계단 오르기 - Java]

문제 분석

DP

시간 복잡도

DP를 이용하면 O(N)에 해결 가능

구현

1. 테이블 정의

int[][] table = new int[300+1][2+1];
// table[i][1] = i번째 계단을 연속해서 1개의 계단을 밟고 올라온 경우, 단 현재 계단을 포함해서
// table[i][2] = i번쩨 계단을 연속해서 2개의 게단을 밟고 올라온 경우, 단 현재 계단을 포함해서

2. 점화식 구하기

table[i][1] = Math.max(table[i-2][2], table[i-2][1]) + stair[i]; //...1
table[i][2] = table[i-1][1] + stair[i]; //...2

1. 현재 계단을 포함해서 연속해서 1개의 계단을 밟았다는 의미이다. 즉, 2계단 밑의 계단에서 해당 계단으로 왔다는 의미이다.

2. 현재 계단을 포함해서 연속해서 2개의 계단을 밟았다는 의미이다. 즉, 1계단 밑의 계단에서 해당 계단으로 왔다는 의미의다. 현재의 계단을 포함해서 연속해서 2개의 계단을 밟았기 때문에 table[i-1][2] 는 고려대상에서 제외된다. table[i-1][2]는 이미 i-1번째 계단까지 연속해서 2개의 계단을 밟았을 때의 점수이기 때문에 table[i-1][2]를 고려하게 되면 연속해서 3개의 계단을 밟는 경우도 고려하게 되는 꼴이 된다.

3. 초기값 설정

table[1][1] = stair[1];
table[1][2] = -1; // 논리적으로 말이 안되는 상황.

table[2][1] = stair[2];
table[2][2] = stair[1] + stair[2];

헤맸던 부분

풀이를 못봤다면, 풀지 못했을 것 같다... 헤맸다기보다는 아예 못 풀었다.

다른 접근 방법

위 강의에서 2가지 풀이 방법을 설명해주신다.

바킹독님 강의

얻은 것

• 사실, 이 문제를 통해서는 지식을 얻었다기 보다는 DP라는 것이 단순히 풀이 방법을 익혀서 늘지는 않겠다는 깨달음을 얻었다.
• 결국, 테이블을 정의하고, 점화식을 세우는 연습을 많이 해야 할 것 같다.

전체 코드 [ 내 코드 - Java ]

느낀점

DP는 지름길이 없는 것 같다. 정말 많은 문제를 풀어보는 방법 밖에는 없는 것 같다.

참조

바킹독님의 실전 알고리즘 강의