[백준/1010/다리 놓기]

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

1010번: 다리 놓기

 

 

<<풀이>>

 

이 문제는 DFS로 풀었다. 처음에는 시간 초과가 났는데 메모제이션을 활용한다면 이를 극복할 수 있고 메모리 초과 같은 경우는 내가 다리가 놓아질 수 있는 최대 갯수를 확인 안 하고 무작정 높게 잡아서 생긴 문제이다. 이런 부분만 조심하면 바로 구할 수 있다!!

 

메모제이션을 활용할 때 조합쳐럼 nCr 에 특정 n, r일 때의 값을 저장해야 하기 때문에 이중배열을 사용해서 메모제이션을 활용했다.

 

외에는 조합을 풀기 위한 정형적인 방식이다 !!

 

nCr = n-1Cr + n-1Cr-1

 

이 공식을 잘 기억해두자!

import java.util.Scanner;

class Data {
    int a;
    int b;
    public Data(int a, int b) {
        this.a = a;
        this.b = b;
    }
}
class Main {
    public static int[][] ch = new int[50][50];

    private int DFS(int b, int a, int n) {
        if (ch[b][a] > 0) return ch[b][a];
        for (int i = 0; i < n; i++) {
            if (b == a || a == 0) return 1;
            else return ch[b][a] = DFS(b - 1, a - 1, n) + DFS(b - 1, a, n);
        }
        return -1;
    }


    public static void main (String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        Data[] data = new Data[n];
        for (int i = 0; i < n; i++) {
            data[i] = new Data(in.nextInt(), in.nextInt());
        }
        for (int i = 0; i < n; i++) {
            System.out.println(T.DFS(data[i].b, data[i].a, n));
        }

    }
}