[자바] 백준 1010번 다리 놓기

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

 

[문제 이해]

동적 프로그래밍 문제였다. nCr 을 생각해내면 풀 수 있는 문제였는데 완전 잊고 있었다,, 재귀로도 풀 수 있고 반복문으로도 풀 수 있는데 재귀보다는 반복문을 사용해서 푸는 방식을 선택했다.

 

[문제 풀이]

이차원 배열로 나타내면

1C0 1C1

2C0 2C1 2C2

3C0 3C1 3C2 3C3

.

.

.

이런 느낌이니까 가장 앞줄 즉, arr[i][0]과 가장 마지막 즉, arr[i][i]의 값은 1로 넣어주고 나머지 값은 [i-1][j] + [i-1][j-1] 값을 저장해주면 된다. 이를 통해 입력된 값 중 큰 값을 행의 인덱스로 지정해서 출력하면 된다.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {
        int max = 30;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());


        int[][] arr = new int[max + 1][max + 1];

        for(int i = 1; i <= max; i++){
            arr[i][i] = 1;
            arr[i][0] = 1;
        }

        for (int i = 2; i <= max; i++){
            for (int j = 1; j <= max; j++){
                arr[i][j] = arr[i-1][j] + arr[i-1][j-1];
            }
        }
        
        for(int i = 0; i < T; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int N = Integer.parseInt(st.nextToken());
            int M = Integer.parseInt(st.nextToken());

            if(N > M){
                bw.write(String.valueOf(arr[N][M]) +"\n");
            }
            else{
                bw.write(String.valueOf(arr[M][N]) +"\n");
            }
        }

        br.close();
        bw.flush();
        bw.close();
    }
}