그랬었습니다

계단을 오르는 방법은 2가지 방법이 있다. 한 계단씩 오르는 방법과 두 계단씩 오르는 방법. 그리고 제약조건으로 "연속된 세 개의 계단을 모두 밟아서는 안된다."가 있다. 조금 관점을 바꿔서, 올라올 계단의 입장에서 보자. 올라오는 방법은 한 계단 아래에서 올라오는 방법과 두 계단 아래에서 올라오는 방법이 있다. 그리고 s[i][1]을 "가장 마지막에 한 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"라고 정의하자. s[i][2]는 "가장 마지막에 두 계단 아래에서 올라와서 i번째 계단으로 올라갔을 때의 최고 점수"이다. 그럼 s[i][1]을 살펴보자. 한 계단 아래에서 올라왔다. 즉 i - 1번째 계단과 i번째 계단을 밟았다는 것이다. 따라서 이 방법을 골랐을 경우에는 i - 1번째 ..