[BOJ] 1010 다리놓기

1010 다리놓기 

1010번: 다리 놓기

 

Explanation

문제를 마주했을 때 아무 생각도 안난다면 일단 경우의 수를 나열해서 규칙을 찾아보자.

N	M	경우의 수
1	1	1
1	2	2
1	3	3
...	...	...
2	2	1
2	3	3	2+1
2	4	6	3+2+1
2	5	10	4+3+2+1
...	...	...
3	3	1	1
3	4	4	(2+1)+1
3	5	10	(3+2+1)+(2+1)+1
3	6	20	(4+3+2+1)+(3+2+1)+(2+1)+1
...	...	...

 

M이 증가할 때마다 일정한 규칙으로 다리를 지을 수 있는 경우의 수가 증가함을 알 수 있다.

이를 수식으로 나타내면

 

DP[N][M]: 강 서쪽에 N개의 다리가 있고, 강 동쪽에 M개의 다리가 있을 때 다리를 겹치지 않게 놓을 수 있는 경우의 수

N	M	경우의 수
N	N	DP[N-1][N-1]
N	N+1	DP[N-1][N] + DP[N-1][N-1]
N	N+2	DP[N-1][N+1] + DP[N-1][N] + DP[N-1][N-1]
...	...	...
N	M	DP[N-1][M-1] + DP[N-1][M-2] + ... + DP[N-1][N-1]

위와 같은 규칙을 찾을 수 있다.

그리고 위 식을 정리하면

N	M	경우의 수
N	N	DP[N-1][N-1]
N	N+1	DP[N-1][N] + DP[N][N]
N	N+2	DP[N-1][N+1] + DP[N][N+1]
...	...	...
N	M	DP[N-1][M-1] + DP[N][M-1]

 

DP[N][M] = DP[N-1][M-1] + DP[N][M-1] 수식을 찾아낼 수 있다.

이를 활용하여 문제를 해결할 수 있다.

그런데 이 수식 조합(Combination) 수식과 똑같다.

조합의 경우의 수를 해결할 때 동적 프로그래밍(Dynamic Programming) 방식을 이용하여 해결할 수 있는것이다.

그렇다면 어떻게 이 문제가 조합문제와 같을까?

 

조합이란 집합에서 일부 원소를 취해 부분집합을 만드는 방법을 뜻한다. 죽 전체 원소가 N개 이고 R개를 뽑는 경우의 수 이다. 중요한 점은 이 때 순서를 고려하지 않는다. 

다리 문제에서도 강 동쪽의 M개의 사이트 중 N개의 사이트를 선택하는 문제와 같다. 그리고 다리끼리는 서로 겹칠 수 없다는 조건은 선택한 N개의 사이트의 순서를 고려하지 않는다는 뜻이 된다. 

Code

소스코드

import java.util.Scanner;

public class BOJ_1010 {

    static class Solution {
        // bridge[N][M]: 강 서쪽에 N개, 강 동쪽에 M개의 다리가 있을 때 다리를 지을 수 있는 경우의 수
        int[][] bridge;

        public void solve() {
            initBridge();
            Scanner sc = new Scanner(System.in);
            int testCase = sc.nextInt();
            for (int t = 0; t < testCase; t++) {
                int N = sc.nextInt();
                int M = sc.nextInt();
                System.out.println(bridge[N][M]);
            }
            sc.close();
        }

        private void initBridge() {
            final int SIZE = 30;
            bridge = new int[SIZE][SIZE];
            for (int m = 1; m < SIZE; m++) {
                bridge[1][m] = m;
            }
            for (int n = 2; n < SIZE; n++) {
                for (int m = n; m < SIZE; m++) {
                    bridge[n][m] = bridge[n - 1][m - 1] + bridge[n][m - 1];
                }
            }
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.solve();
    }

}

Related Topics

#combination #Dynamic Programming