다이나믹 프로그래밍 - 다리 놓기 (백준 1010번)

1.다이나믹 프로그래밍 - 다리 놓기 (백준 1010번)

---

---

2.다이나믹 프로그래밍 & 조합을 이용한 문제풀이

---

1)조합을 이용한 문제풀이

package dynamicProgramming;
 
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;
 
public class Baekjun1010BridgeCombination {
    static BigInteger[] memo=new BigInteger[31];
    static void initMemo(BigInteger[] memo) {
        for(int i=0;i<memo.length;i++) {
            memo[i]=new BigInteger("-1");
        }
        memo[0]=new BigInteger("1");
        memo[1]=new BigInteger("1");
    }
    static BigInteger factorial(int n) {
        if(!memo[n].equals(new BigInteger("-1"))) {
            return memo[n];
        }
        memo[n]=new BigInteger(factorial(n-1).multiply(new BigInteger(n+""))+"");
        
        return memo[n];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        
        for(int i=0;i<T;i++) {
            initMemo(memo);
            int N=sc.nextInt();
            int M=sc.nextInt();
            System.out.println(factorial(M).divide(factorial(M-N)).divide(factorial(N)));
        }
    }
 
}
 

첫번째 풀이는 조합을 이용한 풀이입니다. 예제 입력에서 29개의 다리 중에서 13개의 다리를 겹치지 않고 놓을 경우의 수는 67863913개입니다. 겹치지 않는다? 단순히 그냥 29개의 다리중에 13개의 다리를 뽑는 경우의 수를 구하면 됩니다. 굳이 겹치는 경우를 고려하지 않아도 되는 것입니다. 13C29(13콤비네이션29) 의 값을 구해주는 로직만 짜주면 답은 쉽게 나오게 됩니다.

2)DP를 이용한 풀이

package dynamicProgramming;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class Baekjun1010BridgeUpdateCode {
    static int[][] memo=new int[31][31];
    static void initMemo(int[][] memo) {
        for(int i=0;i<memo.length;i++) {
            for(int j=0;j<memo[i].length;j++) {
                if(i==0) {
                    memo[i][j]=1;
                    continue;
                }
                memo[i][j]=0;
            }
        }
        memo[1][0]=1;
        memo[1][1]=1;
    }
    static int bridge(int n,int m) {
        if(memo[n][m]!=0) {
            return memo[n][m];
        }
        for(int i=m-1;i>=n-1;i--) {
            memo[n][m]+=bridge(n-1,i);
        }
        return memo[n][m];
    }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        StringBuffer sb=new StringBuffer();
        int t=sc.nextInt();
        for(int i=0;i<t;i++) {
            int n=sc.nextInt();
            int m=sc.nextInt();
            initMemo(memo);
            sb.append(bridge(n, m)+"\n");
        }
        System.out.println(sb);
    }
 
}
 

예를 들어 서쪽에는 3개의 사이트 동쪽에는 5개의 사이트가 있다고 가정한다면 bridge(3,5) 메소드를 호출하게 된다. 여기서 반복문이 뜻하는 바는 i==4부터 i==2까지 값을 감소시키며 bridge 함수를 호출시키는 것이다. 이것은? i==4라면 서쪽의 첫번째 사이트가 동쪽의 1번 사이트와 다리가 연결되어 남은 2개의 서쪽사이트와 4개의 동쪽사이트로 연결할 수 있는 다리의 경우를 구하면 되는 것이고, i==3이면 서쪽의 1번 사이트가 동쪽의 2번사이트와 연결되어 남은 2개의 서쪽사이트와 동쪽의 2번 밑의 3,4,5 3개의 사이트와 연결될 경우의 수를 구한다. 이렇게 쭉쭉가다가 서쪽과 동쪽의 남은 사이트 수가 같을 때까지 반복한다. 이런 것이 서쪽 사이트가 하나씩 줄어 가며 반복되는 것이다. 그리고 마지막 서쪽사이트가 함수에 들어 오게 된다면 초기화된 값을 바탕으로 memo[n][m]의 값을 구하게 되는 것이다.