백준(BOJ) 1010번 다리놓기

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

 

 

조합을 사용하여 정말 간단히 풀리는 문제다. 내가 조합을 공부할 때는 이보다 훨씬 복잡했다. 조합을 재귀트리로 구현할때 어떻게 구현하는지와 아래와 같이 dp를 써서 구현할 때 어떻게 저런 수식이 나오는지 그리고 시중의 다른 풀이법에 대하여 공부하자.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main{
    public static int solution(int r, int n){
        int[][]dp=new int[n+1][r+1];
        for(int i=1;i<=n;i++){
            for(int j=0;j<=r;j++){
                if(j==i ||j==0)
                    dp[i][j]=1;
                else
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
            }
        }
        return dp[n][r];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(br.readLine());
        StringTokenizer st;
        for(int t=0;t<T;t++){
            st=new StringTokenizer(br.readLine());
            int west=Integer.parseInt(st.nextToken());
            int east=Integer.parseInt(st.nextToken());
            System.out.println(solution(west, east));

        }

    }
}