섹션 10. dynamic programming(동적계획법) 2. 돌다리 건너기

문제

• 철수는 학교에 가는데 개울을 만났습니다. 개울은 N개의 돌로 다리를 만들어 놓았습니다.
• 철수는 돌 다리를 건널 때 한 번에 한 칸 또는 두 칸씩 건너뛰면서 돌다리를 건널 수 있습니다.
• 철수가 개울을 건너는 방법은 몇 가지일까요?

입력

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

출력

• 첫 번째 줄에 개울을 건너는 방법의 수를 출력합니다.

입출력 예제

---

풀이방식

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

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

---

설계과정

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

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

3. 개울을 건너는 것은 마지막 돌에서 1번 더 건너야하므로 N+1 이라는 점에 주의해서 dy[N+1]을 출력한다.

---

풀이과정

1.  이전 문제와 동일한 방식이므로 아래 방법을 참고해보자.

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

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

2. 단, 개울을 건너는 것은 마지막 돌에서 1번 더 건너야하므로 dy[ ] 배열의 크기를 N+2로 설정하고 dy[N+1] 을 출력한다.

---

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