섹션 10. dynamic programming(동적계획법) 1. 계단오르기

문제

• 철수는 계단을 오를 때 한 번에 한 계단 또는 두 계단씩 올라간다. 만약 총 4계단을 오른다면 그 방법의 수는
• 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2 로 5가지이다.
• 그렇다면 총 N계단일 때 철수가 올라갈 수 있는 방법의 수는 몇 가지인가?

입력

• 첫째 줄은 계단의 개수인 자연수 N(3≤N≤35)이 주어집니다.

출력

• 첫 번째 줄에 올라가는 방법의 수를 출력합니다.

입출력 예제

---

풀이방식

이번 문제는 동적 계획법(dynamic programming)에 대한 문제이다.

동적 계획법 이란 시간 복잡도가 큰 문제를 직관적으로 작게 나눈다. 이렇게 나누어진 작은 문제들을 메모이제이션을 사용해서 최종적으로 본래 문제의 해결방안을 찾는 것을 말한다.

---

설계과정

1. 1번째, 2번째는 각각 방식이 1개와 2개 뿐이므로 그대로 배열에 넣어서 초기화한다.

2. 3번째부터 N번째까지 돌면서 피보나치 수열처럼 dy[i] 에 ( dy[i-2] + dy[i-1] ) 값을 넣어준다.

3. dy[N] 을 출력한다.

---

풀이과정

1.  dy[ ] 배열 1,2번째에 1, 2를 넣어서 각각 초기화한다.

• 1번째 계단과 2번째 계단을 올라가는 방법은 각각 1가지, 2가지 이므로 그대로 값을 넣어서 배열을 초기화한다.

2. dy[1] 과 dy[2] 를 각각 1, 2로 초기화한다.

• 1, 2번째 계단으로 가는 방법은 각각 1개, 2개이다.

3. 3번부터 N번째까지 돌면서 dy[i] 에 ( dy[i-2] + dy[i-1] ) 값을 넣어준다.

• 피보나치 수열과 비슷하다고 보면 된다.
• 큰 문제를 작은 범위로 나눠서 메모리제이션처럼 사용한다.

4. dy[N] 을 출력한다.

---

해당 글은 인프런 > 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비(김태원)강의를 참고하여 작성하였습니다.