gamy0315   3년 전

혹시 저처럼 헤메는 분 계실까봐 적어봅니다.

1. 마지막을 꼭 밟아야 한다? 

-> [마지막계단] -> [첫번째 계단]으로 가자.

2. 테이블로 하면 편하겠다.

-> 현재계단을 2번 연속으로 밟는다 = d[n][2]

-> 1번 밟는다 = d[n][1]

-> 안밟는다 = d[n][0]

(1) d[n][2]

현재 계단을 두번째로 밟으려면 이전 계단을 반드시 밟아야 한다.

d[n][2] = d[n+1][1] + 현재계단

(2) d[n][1]

현재 계단을 첫번째로 밟으려면 이전 계단은 밟으면 안된다.

d[n][1] = d[n+1][0] + 현재 계단

(3) d[n][0]

현재계단을 안밟으려면 이전 계단을 밟아야 한다.

d[n][0] = MAX(d[n+1][1] , d[n+1][2])

3. 만약 마지막 계단을 안밟은게 최대값이면 어떡하지?

d[n][0] = INT 최소값.

다들 즐거운 코딩바래요~

댓글을 작성하려면 로그인해야 합니다.