[Java] 백준(Baekjoon) 1010. 다리 놓기

 

 

---

 

 

풀이

 

0<N<=M<30

1) N=2, M=2 

다리 2개 서로 겹쳐질수 없음

=> 1

 

2) N=1, M=5

다리 1개

=> 5

 

3) 13 29

다리 13개

 

 

1. N, M이 같을 때

DP[1][1] = 1, DP[2][2] = 1, ...

 

2. N = 1일때

DP[1][M] = M

 

3. N=2 일때

DP[2][3]= 3 = 2+1 = DP[2][2]+DP[1][2] = DP[2][2]+DP[1][2] 

DP[2][4]= 6 = 3+2+1 = DP[2][2]+DP[1][2]+DP[1][3] = DP[2][3] + DP[1][3] 

DP[2][5]= 10 = 4+3+2+1

...

DP[2][M] = DP[2][M-1]+(M-1)

 

4. N=3

DP[3][4] = 4 = 2+2 = DP[3][3]+DP[2][3]

DP[3][5] = 10 = 3+4+3 = DP[3][3]+DP[2][3]+DP[2][4] = DP[3][4] +DP[2][4] 

DP[3][6] = 20 = 4+6+6+4

DP[3][7] = 35 = 5+8+9+8+5

...

DP[3][M] = DP[3][M-1]+(M-1)

 

5. N=4

DP[4][5] = 5

 

5. N = 13

DP[13][13] = 1

DP[13][14] = 14

 

=>  DP[i][j]= DP[i][j-1]+ DP[i-1][j-1];

 

package dp;

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

public class Ex1010 {

	static int dp[][] = new int[30][30];
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		for(int i=1;i<30;i++) {
			for(int j=1;j<30;j++) {
				if(i==j) dp[i][j]=1;
				else if(i==1) dp[i][j]=j;
				else {
					dp[i][j]=dp[i][j-1]+dp[i-1][j-1];
				}
			}
		}
		
		int row = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		for(int z=0;z<row;z++) {
			String ex = br.readLine();
			st = new StringTokenizer(ex);
			int n = Integer.parseInt(st.nextToken());
			int m = Integer.parseInt(st.nextToken());
			
			System.out.println(dp[n][m]);
			
		}

	}

}