백준 - 계단 오르기

문제 출처:https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

초기 기획 

조건을 제대로 파악하지 못해서 연속 3계단을 오를 수 있다는 사실을 간과했다..

계단을 오르는 step [] 배열을 만든 후, 초기값으로 인덱스 0 은 10으로 설정해 주었다.

i를 0부터 시작해서 다음과 다다음을 확인하며 이동할 수 있는 최댓값을 갱신하였다. 하지만 앞에서 말했다시피 연속 3계단은 불가능이라는 조건을 간과한 나머지 실패..

 

초기 실패 코드

 

다음에는 왠지 몰라도 이중for문으로 해야 할 거 같아서 해본 결과.. 하면 할수록 knapsack문제인가?..라는 고민과 이건 아닌 거 같다는 생각과 막 꼬이기 시작하면서 그만두게 되었다.

 

 

최종 기획

마지막으로는 다른 분들의 코드를 참고한 결과 제대로된 해결책을 찾을 수 있었다.!

총 4개를 묶어서 확인한다고 생각하면 편하다. 왜냐하면 연속으로 3칸은 불가능하기 때문이다.

③번에는 무엇이 들어가야할까? 확실한 건 ②번에서 단순히 ④번을 더한 값을 넣으면 안 된다.. 왜냐하면 3칸 연속 이동한 것이기 때문이다.

 

그래서 4칸을 크게 범위 잡아서 확인한다.①번과 첫번째 계단 값인 10 중 최댓값을 골라서 ④를 더 해주면 된다.

왜냐고? 

①은 현재 첫 계단을 밝지 않고 바로 두 칸 이동하는 것과 첫 번째 계단 값인 10은 1번 계단을 밝고  이동한 것이다. 이 둘을 비교한다는 것은  ③으로 이동시 1번 계단을 밝고 2칸 연속 이동하느냐, 아니면 2번 계단에서 1칸 이동할 것인가를 정하는 것이다.

결국, 처음부터 2칸 이동하고 다시 한 칸 이동하는 방법이 제일 큰 값으로 ③에 남으므로,  이걸 공식화하면

 

 

step[i] = Math.max(step[i-3]+value[i-1,step[i-2])+value[i]