[JAVA] 조합 DP로 풀기 : 백준 다리놓기

이전까지는 DFS를 이용하여 조합을 구현했다.

참고 : 2021.03.31 - [코딩테스트/Java] - [JAVA] 백준 N과 M(2), DFS 중복X

 

 

이번에는 아래 문제를 통해서 DP(Dynamic Programming, 동적프로그래밍)를 이용하여 조합을 풀어보겠다.

이번 경우에는 시간초과를 해결하기 위해 DP에서 메모이제이션 방식이 사용되었다.

 

다리놓기 문제이다.

www.acmicpc.net/problem/1010

왼쪽에서 N개 오른쪽에서 M개의 점이 주어진다.

https://st-lab.tistory.com/194

M개중 N개를 중복없이 뽑아야되는 문제이다. 그러면 자동으로 순서가 결정된다.

 

이래서 DFS를 통해 문제를 해결하려했다.

하단은 DFS를 이용한 풀이이다. 시간초과했다.

import java.util.Scanner;

public class Main {
    public static int[] arr;
    public static int N, M;
    public static int count=0;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        for(int i=0; i<T; i++) {
            N = in.nextInt();
            M = in.nextInt();
        }
        arr = new int[M];
        dfs(1, 0);

        System.out.println(count);
    }

    public static void dfs(int at, int depth) {
        if (depth == M) {
            count++;
            return;
        }

        for (int i = at; i <= N; i++) {
            arr[depth] = i;
            dfs(i + 1, depth + 1);
        }
    }
}

 

그래서 구현한 방법이 DP 방식이다.

 

조합성질에서 꼭 잊지말아야 할 두가지이다!!! 꼭 잊지말자.

조합성질1

조합성질2

첫번째 포인트는 위 조합성질을 이용하는것.

 

두번째 포인트는 dp배열을 통해 메모이제이션 return을

 int[][] dp = new int[30][30];//적당한 크기
 
 
 //리턴주목 : 배열에 넣어준다.
 static int comb(int n, int r) {
        if (dp[n][r] > 0) {//메모이제이션 포인트!!!!!!!!!!!
            return dp[n][r];
        }
        if (r == 0 || n == r) {
            return dp[n][r] = 1;
        }

        return dp[n][r]= comb(n - 1, r - 1) + comb(n - 1, r);

    }

 

위처럼 이용해주는것이다.

반응형

 

<메모이제이션 설명>

 

1. 메소드 가장 윗부분에 메모이제이션에서 이미 방문했다면 해당 dp배열값을 바로 리턴해줌으로써 시간절약을 한다.

 

2. nCr에서 (r=0)일때와 n=r인경우)에 1로 최종 방문표시(끝까지 탐색함dfs) return할때도 dp에 넣어주고

 

3. 마지막에는 재귀부분으로 이어지는 부분도 dp배열에 계속해서 넣어준다.

 

 

최종코드 dfs+메모이제이션

import java.util.Scanner;

class Main {
    static int[][] dp = new int[30][30];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        StringBuilder sb = new StringBuilder();
        int T = in.nextInt();
        for (int i = 0; i < T; i++) {
            int N = in.nextInt();
            int M = in.nextInt();
            sb.append(comb(M, N)).append('\n');
        }

        System.out.println(sb.toString());
    }

    static int comb(int n, int r) {
        if (dp[n][r] > 0) {
            return dp[n][r];
        }
        if (r == 0 || n == r) {
            return dp[n][r] = 1;
        }

        return dp[n][r]= comb(n - 1, r - 1) + comb(n - 1, r);

    }

}