[백준][silver5][JAVA] 1010-다리 놓기

[문제 설명]

www.acmicpc.net/problem/1010

1010번: 다리 놓기

 

[풀이 과정]

M개 중에 N개 선택하여 조합하는 경우의 수를 구하는 문제다. 

조합 경우의 수를 구하는 방법은 여러가진데 메모이제이션을 이용하면 가장 효율적으로 풀 수 있다. 

 

* 메모이제이션을 이용한 조합 경우의 수 구하기 

- 메모이제이션(memoization) 기법은 동적 프로그래밍의(dynamic programming)의 일종이다. 

메모를 할 배열을 만들어 놓고 처음 계산한 값은 배열에 저장한다. 

이후 같은 계산을 반복할 때 다시 계산하지 않고 배열에 저장된 값을 바로 꺼내 사용한다. 

 

* 이항계수

조합은 이항계수라는 성질을 가지고 있다. 

nCr 이라는 조합이 있을 때,

- n==r 또는 r==0 일 때, nCr = 1
- 그 외, nCr = n-1Cr-1 + n-1Cr

 

메모이제이션과 이항계수로 조합을 구하면 다음과 같다. 

public static int combination(int n, int r, int[][] memo) {
        if (n==r || r==0) {
            return 1;
        }

        if (memo[n][r] > 0) {
            return memo[n][r];
        }

        memo[n][r] = solution(n-1, r-1, memo) + solution(n-1, r, memo);
        return memo[n][r];
}

 

느낀점:

조합으로 구할 수 있는 모든 원소들의 패턴을 나열하라고 하면 완전탐색이 맞다. 

하지만 개수를 구하는 것이라면 동적프로그래밍으로 풀어야 효율성이 좋다. 

 

[JAVA code]

package com.algorithm.baekjoon.silver4;

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

public class Test03 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        StringTokenizer st;
        for (int i = 1; i <= N; i++) {
            st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
            int[][] memo = new int[m + 1][n + 1];

            int answer = solution(m, n, memo);
            System.out.println(answer);
        }
    }

    public static int solution(int m, int n, int[][] memo) {
        if (m == n || n == 0) {
            return 1;
        }

        if (memo[m][n] > 0) {
            return memo[m][n];
        }

        memo[m][n] = solution(m - 1, n - 1, memo) + solution(m - 1, n, memo);
        return memo[m][n];
    }
}