[백준/자바] dp 1010번 - 다리 놓기

• 문제

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

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

 

 

 

• 풀이

n개의 다리 중에서 r개를 선택하는 경우의 수 문제다. 그 중에서도 한 사이트당 하나의 다리만 연결되어 중복이 불가하고, 다리끼리 겹칠 수 없다는 조건으로 인해 고정된 순서대로 연결되어, 순서 고려 없이 선택하는 조합 문제다.

조합에 대해 기억하고 있는 공식이 nC0 = nCn = 1 밖에 없어서 다시 조합, 파스칼의 삼각형을 공부하며 문제를 풀었다. 아래 참고한 블로그가 문제를 풀고 이해하는 데 도움이 많이 됐다. 

 

 

출처 :  https://blog.naver.com/vollollov/220947452823

 

nC0 = nCn = 1

n+1Cr+1 = nCr + nCr+1

 

이 두가지 공식을 활용해서 bottom-up, top-down 방식으로 풀어봤다.

 

bottom-up 방식으로는 dp 배열에 미리 값을 다 저장해둔 후 입력을 받도록 했다. 행, 열 사이즈가 30 미만으로 제한되어 있기도 하고 위치마다 고정된 값(파스칼 삼각형)을 이용하는 것이므로, 입력할 때마다 배열을 초기화하는 것은 비효율적이라고 생각했다. 

 

/* 서쪽 사이트 - 동쪽 사이트 잇는 다리 지을 때 경우의 수 (0<w<=e<30)
 * 한 사이트당 하나의 다리만 지음, 서쪽 사이트 수만큼 다리 지음, 다리끼리 겹쳐질 수 없음
 * => 조합 (eCw)
 * 입력 1 : 테스트케이스 개수
 * 입력 2 : w e (w: 서쪽 사이트 수, e: 동쪽 사이트 수)
 */
public class BuildingBridge {

    static int[][] dp = new int[30][30];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        /* 조합 공식 활용 (eCw)
         * eC0 = eCe = 1
         * e+1Cw+1 = eCw + eCw+1
         * */
         
        // 공식 1 활용 - 미리 1 저장 
        for (int i=0;i<30;i++){
            dp[i][i] = 1;
            dp[i][0] = 1;
        }
		
        // 공식 2 활용 - 파스칼 삼각형 값 순차적으로 저장
        for (int i=2;i<30;i++){
            for (int j=1;j<30;j++){
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }

        int T = Integer.parseInt(br.readLine());
        for (int i=0;i<T;i++){
            st = new StringTokenizer(br.readLine(), " ");

            int w = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());

            System.out.println(dp[e][w]);
        }
    }

/*    private static int countBridgesWithRecursion(int e, int w) {
        if (dp[e][w] > 0) return dp[e][w]; // 배열에 저장된 값은 바로 반환

        if (w == 0 || w == e) return dp[e][w] = 1; // 공식 1 활용

        return dp[e][w] = countBridgesWithRecursion(e-1, w-1) + countBridgesWithRecursion(e-1, w); // 공식 2 활용
    }*/

}

 

 

 

• 참고

https://blog.naver.com/vollollov/220947452823