[Java/백준/DP] 1010번: 다리 놓기

문제

www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

코드 1(DP를 사용하지 않는 방법)

조합 공식을 그대로 사용했다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

class Main{
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		
		int T = Integer.parseInt(br.readLine());
		
		for(int i=0; i<T; i++) {
			String[] str = br.readLine().split("\\s");
			int N = Integer.parseInt(str[0]);
			int M = Integer.parseInt(str[1]);
			
			if(N==M)
				sb.append("1\n");
			else {
				int tmp = 1;
				for(int j=1;j<=N;j++) {
					tmp=tmp*(M-j+1)/j;
				}
				sb.append(Integer.toString(tmp)+"\n");				
			}
		}		

		bw.write(new String(sb));
		bw.flush();
	}
}

 

코드2 (DP 사용)

참고 링크

m.blog.naver.com/PostView.nhn?blogId=occidere&logNo=220876138317&proxyReferer=https:%2F%2Fwww.google.com%2F

[백준] 1010 - 다리 놓기

 

이걸 어떻게 생각하지.....? 갈길이 멀다 DP....