[BOJ][DP] 1010. 다리 놓기

문제 -> https://www.acmicpc.net/problem/1010

이 문제는 DP를 활용한 풀이와 확통의 조합을 사용하여 해결할 수가 있다.

하지만 나는 그냥 DP로 풀어버렸다. 

이왕 DP문제인데 DP로 풀어야 재밌지..

다른 사람들은 죄다 조합으로만 풀더이라. 

(물론, 확실히 조합이 더 빨라서 그런거겠지만.)

위 그림의 사이트 상태는 

N: 3, M: 4 다.

어라? 가만보면 

그 속에 (2,3)과 (2,2)가 들어있다.

옳지. 

이를 통해 알 수 있는 사실은

전에 계산했던 값들을 이용하여 새 DP값을 얻을 수 있다는 것.

일단 N이 1인 경우의 수들을 구해둔 상태를 전제로 해야한다.

위 그림의 동그라미 친 부분처럼,

부분적인 경우의 수가 더 이상 없을때까지 

계속 더해야한다. 

더하는 식은 dp[i][j] =+= dp[i-1][k] 로 세우면 되고

언제까지 더하느냐. 

경우의 수가 더 이상 없을 때까지니까,

i-1 == k 일때까지 더해주면 된다.

소스(GitHUb)