백준 1010번 다리 놓기

< 백준 1010번 다리 놓기 - 마포 코딩박 >

사용한 알고리즘: DP


 강의 서쪽에 N개, 동쪽에 M개의 사이트가 있을 때, N개의 다리를 놓을 수 있는 경우의 수를 구하는 문제입니다.

문제풀이는 다음과 같습니다.

(1) (코드 5~6)
 'dp[a][b] = 서쪽 a개, 동쪽 b개 일때 a개의 다리를 놓을 수 있는 경우의 수' 로 설정했습니다.

(2) (코드 9~10)
 초기값 dp[1][i] = i 입니다. 즉 서쪽 1개, 동쪽 i 개 일때, 1개의 다리를 놓는 경우는 i가지 입니다.

(3) (코드 11~20)
 동쪽 i개, 서쪽 j개 인 경우수는 (i-1)(j-1), (i-1)(j-2), ... (i-1)(j-1) 의 각 경우에다 위에 다리 하나 더 놓는경우라고 생각할 수 있습니다.
 즉 dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + ... + dp[i-1][i-1] 입니다.
 ( dp[i][j] 에서 i>j 인 경우수는 0 입니다. )
 예를들어 dp[3][5] = dp[2][4] + dp[2][3] + dp[2][2] 입니다.
 이를 통해 dp값을 계산합니다.