2579번 - 계단 오르기
혹시 저처럼 헤메는 분 계실까봐 적어봅니다.
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 최소값.
다들 즐거운 코딩바래요~
댓글을 작성하려면 로그인해야 합니다.
gamy0315 3년 전 2
혹시 저처럼 헤메는 분 계실까봐 적어봅니다.
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 최소값.
다들 즐거운 코딩바래요~