[DP기초] 계단오르기

 

코드없는 프로그래밍 님의 DP강의 중  최소비용 계단오르기 강의를 참고하여 작성했습니다

https://www.youtube.com/watch?v=lhZTYwHgrDM&list=PLDV-cCQnUlIa0owhTLK-VT994Qh6XTy4v&index=3 

계단이 n개까지 있을 때, n층에 올라갈 수 있는 방법은 f(n)=f(n-1)+f(n-2)이다. 

f(1)=1

f(2)=2 --> 한칸 씩, 한번에 올라가는

f(3)=3

등등이다.

 

그러면 가장 최소비용으로 계단을 올라가는 방법을 알아보자. 

[1,2,4,6,2] 의 5층의 계단이 있다. 

 

f(0)=0+1이다 왜냐하면 바닥에서 한번에 올라갈 수 있고, arr[0]=1(여기서 arr[0]은 0층의 값을 나타냄) 이므로 0+1=1이다.

f(1)=0이다. 얘도 바닥에서 한번에 올라갈 수 있기 때문에 0+2이다.

f(2)는 에서 올라가거나 f(2)에서 올라갈 수 있다. f(2)=Math.min(f(0),f(1)) 즉 f(2)=1

이렇게 f(n)까지 해나가면 된다!

문제로 풀어보기 

---

 

 

https://www.acmicpc.net/problem/2579

2579번: 계단 오르기

 

https://we1cometomeanings.tistory.com/88

[java 백준] 실버 3/ 2579번 계단오르기

백준 2579번 문제는 최대비용 계단오르기이다. 참고하면 좋을듯하다.