2. 다리 놓기(동적계획법) 알고리즘 (Baek-Joon 사이트 1010번)

1. 문제

문제출처: https://www.acmicpc.net/problem/1010

2. 출력

2-1) 전체코드

2-2) 출력

2-3) 결과

3. 해설

 결국 동적계획법, 즉 다이나믹 프로그래밍(Dynamic Programming)이다.

 다리끼리 서로 겹칠 수 없는 조건이기 때문에 쉽게 풀릴 수 있다.

 만약 다이나믹 프로그래밍을 하지 않는다면 엄청난 시간 계산이 소요된다.

 결국 이것도 피보나치 수열과 다를 게 없다.

 N과 M이 같을 때 무조건 1나의 경우의 수만 존재하며 또한

 N이 1일 때, 경우의 수는 무조건 M이다.

 이 사실을 토대로 요구하는 결과값이 나올 때까지 테이블을 채워나가면 된다.

 코드에 써놓은 예제의 규칙대로 작성하면 된다.

 EX) Table[3][5] = Table[2][4] + Table[2][3] + Table[2][2] 이다.

 이유는 한 번 그려보면 된다.

 결국 동적계획법, 즉 Dynamic Programming은 작은 연산에서부터 큰 연산을 만들어 낼 수 있으면 가능한 것!