백준/1010 다리놓기 // 파스칼 삼각형 + 다이나믹프로그래밍

다리 놓기 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

128 MB

64625

29963

24502

48.438%

문제

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

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

입력

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.

출력

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

예제 입력 1 복사

3
2 2
1 5
13 29

예제 출력 1 복사

1
5
67863915

---

 풀이

    //서쪽에 있는 다리가 동쪽에 있는 다리를 선택하는 느낌이다.
    //서쪽에 하나의 다리가 동쪽에 어떤 다리를 골랐을 경우  선택된 다리 이후의 것만을 고려해야한다.
    //이것은 조합의 진행 방식과 같다. 반복문의 시작인덱스를 매개변수로 전달해주고, 전달할때 +1 해주니까
    //서쪽다리를 기준으로 동쪽의 다리를 뽑고, 한뽑고를 진행하면 된다. 조합의 진행순서상 다리가 엇갈리는 경우는 나오지않는다.

 라는 생각으로 조합으로 풀이를 해보았다.

하지만 시간초과가 발생

해당 코드는 아래와 같다.

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    //서쪽에 있는 다리가 동쪽에 있는 다리를 선택하는 느낌이다.
    //서쪽에 하나의 다리가 동쪽에 어떤 다리를 골랐을 경우  선택된 다리 이후의 것만을 고려해야한다.
    //이것은 조합의 진행 방식과 같다. 반복문의 시작인덱스를 매개변수로 전달해주고, 전달할때 +1 해주니까
    //서쪽다리를 기준으로 동쪽의 다리를 뽑고, 한뽑고를 진행하면 된다. 조합의 진행순서상 다리가 엇갈리는 경우는 나오지않는다.

    static int count;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int westBridges = Integer.parseInt(input[0]);
            int eastBridges = Integer.parseInt(input[1]);
            visited = new boolean[eastBridges];
            combination(eastBridges, westBridges, 0);
            bw.write(count + "\n");
            count = 0;
        }

        bw.flush();
        bw.close();

    }

    public static void combination(int n, int r, int start) {
        if (r == 0) {
            count++;
            return;
        }
        for (int i = start; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                combination(n, r - 1, i + 1);
                visited[i] = false;
            }
        }
    }

}

 

시간초과가 난이유는?

일단 시간제한은 0.5초이고

테스트케이스는 몇개가 나올지 모른다.

다리의 최대갯수는 30개라고 한다.

조합의 시간복잡도는 O(2^N) 이므로

2의 30승  1,073,741,824 약 10억 ,  다리가 30개일경우 조합계산에만 약 10초가 걸린다.

여기서 시간초과가 발생하였다.

그렇다면 어떻게 해야 조합을 할때 시간이 별로 안걸릴까

 

해답 : 파스칼 삼각형

nCr = n-1Cr + n-1Cr-1 이기 때문에 해당 식을 이용하여 풀이한다.

 

30C5= 29C5 + 29C4 이고 29C5 는 28C5 + 28C4이기 떄문에 

큰 문제를 작은문제로 나눠서 풀이하는 다이나믹 프로그래밍을 이용한다.

작은문제들을 dp배열에 저장해서(메모이제이션)  큰문제를 해결해보자.

 

바텀업, 탑다운 둘다 사용해보자.

 

 

바텀업

import java.io.*;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int count;
    static int[][] paskalTriangle;
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int westBridges = Integer.parseInt(input[0]);
            int eastBridges = Integer.parseInt(input[1]);
            paskalTriangle = new int[eastBridges+1][eastBridges+1];
            combination(eastBridges, westBridges);
            bw.write(paskalTriangle[eastBridges][westBridges]+"\n");


        }

        bw.flush();
        bw.close();

    }

    public static void combination(int n,int r) {
       //바텀업으로 파스칼삼각형 각각의 값을 채운다.
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= r; j++) {
                if (i == j || j == 0) {
                    paskalTriangle[i][j] = 1;
                } else{
                    paskalTriangle[i][j] = paskalTriangle[i - 1][j] + paskalTriangle[i - 1][j - 1];
                }
            }
        }
    }

}

 통과

 

탑다운

import java.io.*;


public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static int count;
    static int[][] paskalTriangle;
    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            String[] input = br.readLine().split(" ");
            int westBridges = Integer.parseInt(input[0]);
            int eastBridges = Integer.parseInt(input[1]);
            paskalTriangle = new int[eastBridges+1][eastBridges+1];
            combination(eastBridges, westBridges);
            bw.write(paskalTriangle[eastBridges][westBridges]+"\n");


        }

        bw.flush();
        bw.close();

    }

    public static int combination(int n,int r) {
       //탑다운 방식 원하는값을 얻기위해 맨 아래 기저값까지 내려갔다가 dp배열을 채우면서 올라오고 결국 원하는 값을 얻는 방식
        if (n == r || r == 0) { //n과 r이 같거나 r이 0이라면 경우의 수는 1이므로
            paskalTriangle[n][r] = 1; //파스칼삼각형의 해당 위치는 1로 채우고
            return paskalTriangle[n][r]; //그 값을 리턴해준다.
        }
        else{ //아니라면
            if (paskalTriangle[n][r] == 0) { //삼각형 해당위치의 값이 비어있다면
                paskalTriangle[n][r] = combination(n - 1, r) + combination(n - 1, r - 1); // 재귀를 이용하여 채워준다.
            }
            return paskalTriangle[n][r]; // 방금 위에서 채워줬거나 , 아니면 원래 채워져있었다면 그 값을 리턴한다.
        }
    }

}