(Java) 백준 1010번 - 다리놓기

https://www.acmicpc.net/problem/1010

문제

> 재원이는 한 도시의 시장이 되었다. 
> 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다. 
> 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리를 짓기로 결심하였다. 
> 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다.
> 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N ≤ M)

> 재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다.
(이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 
> 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다.
> 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

접근

파스칼의 삼각형 성질의 이용하여 dp로 풀 수 있다.
(M,N)으로 삼각형을 그려보면 (1,1)은 1가지, (2,1)은 2가지, (2,2)는 1가지, (3,1)은 3가지, (3,2)는 3가지, (3,3)은 1가지, (4,1)은 4가지, (4,2)는 6가지, (4,3)은 4가지, (4,4)는 1가지 인걸 직접 구할 수 있다.
이를통해 규칙을 찾아보면 M,1은 M가지의 경우의 수를 가지고,
M,M은 1가지의 경우의 수만 가진다, 이제 M이 3일 때 부턴 (3,2)가 (2,1)과 (2,2)의 합이라는 걸 알 수 있다.
즉 식으로 써보면 (M,1) = M, (M,M) = 1, 이를 제외한 (M,N)은 (M-1, N-1) + (M-1, N)이 된다.

문제해결

> 주어진 모든 범위인 0보다 크고 30보다 작은 범위에 대해 가능한 경우를 dp로 모두 구한다.
> i는 M을 나타내고 j는 N을 나타낸다. M,M과 M,1에 대해 먼저 처리해준다.
> 3,2부터 파스칼의 삼각형 성질을 쓸 수 있기 때문에 이 때 부터 앞서 유도한 공식을 대입한다.
> 테스트 케이스마다 N과 M을 입력받고 미리 구한 dp에서 뽑아다 출력해준다.

코드

import java.io.*;
import java.util.*;
import java.lang.*;

public class Main
{
    //1010번 다리 놓기
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int[][] dp = new int[30][30];
        for(int i = 1; i < 30; i++)
        {
            dp[i][i] = 1;
            dp[i][1] = i;
            for(int j = 2; j <= i-1; j++) dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
        }
        
        int T = Integer.parseInt(br.readLine());
        while(T-->0)
        {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            sb.append(dp[M][N]).append('\n');
        }
        System.out.print(sb);
    }
}

후기

맞게했는데 왜 안나오나 해서 다시 봤더니 출력부에서 M과 N을 반대로 썼다.