(JAVA) 백준 문제 풀이 - 조합론 단계 - 1010번 다리 놓기 (실버 5)

이번 문제는 주어진 테스트 케이스의 각각의 경우의 수를 출력하는 문제이다.

위 문제를 풀기 위해서는 이항 계수를 이해할 필요가 있는데 수학을 조금 아는 사람이라면 로직 자체는 어렵지 않기 때문에 금방 풀 수 있을 것이다.

하지만 나는 수학에 손을 놓은지 꽤 된 터라... 문제를 이해하는데 꽤나 애를 먹었다.

그러면 이항계수가 무엇이고 이를 이용하여 어떻게 문제를 풀어야 하는지 알아보자.

---

이항 계수(Binomial Coefficient)란?

en.wikipedia.org/wiki/Binomial_coefficient

Binomial coefficient - Wikipedia

이항 계수에 대한 정확한 개념은 위 글에 잘 정리가 되어있다.

 

이항계수란 주어진 크기의 집합에서 원하는 개수만큼 순서없이 뽑는 조합의 가짓수를 말한다.

전체 집합에서 원수의 개수 n에 대해 k개의 아이템을 뽑는 이항계수는 다음과 같이 정의 할 수 있다.

위 공식을 이용하여 4개의 집합 중에서 2개를 순서없이 고르는 조합의 수는 '4!/(4-2)!/2! 이므로 6이라는 것을 알 수 있다.

그런데 위의 식을 이용하는 경우 각각에 수에 대해서 Factorial을 전부 구해야하는 번거로움이 생긴다.

따라서, 위의 식을 이용하는게 아니라 이항계수의 성질을 이용하여 알고리즘을 짜는것이 더 유리하다고 볼 수 있다.

사용될 이항계수의 성질은 다음과 같다.

 

첫번째 성질

위 공식을 조금더 간단하게 변경한다면 다음과 같다.

그리고 n과 r에 대하여 정리하면 다음과 같이 보여진다.

위 점화식을 흔히 '파스칼의 법칙'이라고 부른다.

 

두번째 성질

만약, n = r인 경우 r = 0이라면 1이 될 것이다.

그리고 위의 식을 좀더 간단하게 표현하면 다음과 같이 표현할 수 있다.

그럼 위의 두가지 성질을 코드로 표현해보자.

int BC(int n, int k) {
	if(n == k || k == 0) {
    	return 1;
    }
    
    return BC(n-1,k-1) + BC(n-1,k);
}

위와 같이 재귀를 통하여 이항 계수를 구할 수 있다.

 

자, 그럼 이제 문제를 풀면 되느냐?

아니다. 한가지 문제가 더 남아있다.

재귀로 푸는 경우 이미 풀었던 문제를 다시 푸는 경우가 생길 수 있기 때문에 memoization(메모이제이션)을 하지 않으면 함수의 성능이 매우 떨어지게 된다.

따라서, 함수의 효율을 높이기 위해서 메모이제이션이 필요하다.

그럼 무엇을 해야하는가?

여기서 나오는 것이 동적계획법이다.

쉽게 설명하자면 미리 푼 값을 저장해두고 문제를 풀어야 할때만 계산을 하는 형태라고 생각하면 되겠다.

(동적 계획법은 해당 단계에서 자세하게 다시 알아볼 생각이다.)

지금은 그냥 이런게 있구나 정도로만 알고 넘어가도록 하자.

우선 동적 계획법 사용을 위해서는 배열을 선언하고 해당 위치마다 값을 기록 한다.

그리고 값이 있는 경우에만 계산을 하게 하면서 시간 복잡도를 줄이는 것이 핵심이다.

동적 계획법에는 Top-Down과 Bottom-Up 2가지 방식이 있다.

 

1.Top-Down 방식

 
public class Main {
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
 
		System.out.println(BC(N, K));
		
	}
	
	static int BC(int n, int k) {
		
		// 2번 성질
		if(n == k || k == 0) {
			return 1;
		}
 
	    // 1번 성질
		return BC(n - 1, k - 1) + BC(n - 1, k);
	}
}

2. Bottom-Up 방식

public class Main {
 
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
 
		int[][] dp = new int[N + 1][K + 1];
 
		// 2번 성질 (n == k)
		for (int i = 0; i <= K; i++) {
			dp[i][i] = 1;
		}
		
		// 2번 성질 (k == 0)
		for(int i = 0; i <= N; i++) {
			dp[i][0] = 1;
		}
		
 
		for (int i = 2; i <= N; i++) {
			for (int j = 1; j <= K; j++) {
				// 1번 성질 
				dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
			}
		}
 
		System.out.println(dp[N][K]);
	}
}

나는 이중 Top-Down 방식을 사용하여 구현을 하였다.

그러면 문제의 코드를 살펴보자.

 

---

문제 풀이

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

class Main{
    public static int n,a,b;
    public static StringTokenizer st;
    public static int[][] arr;

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

        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            arr = new int[b+1][a+1];
            System.out.println(bc(b,a));
        }

    }

    public static int bc(int n, int k){
        if(arr[n][k] > 0){
            return arr[n][k];
        }

        if(k == 0|| n == k){
            return arr[n][k] = 1;
        }

        return arr[n][k] = bc(n-1,k-1) + bc(n-1,k);
    }
}

코드를 살펴보면 앞선 Top-Down 방식의 코드를 거의 그대로 가져온 것과 비슷하다.

여러개의 테스트 케이스가 주어지기에 반복문을 이용하여 계산할 이항 계수를 받고 그에 따라 2차원 배열을 선언하고 주어진 값을 계산한 후 최종적으로 n,k에 해당하는 배열값을 출력 하는 형태이다.

크게 어려운 코드는 아니였지만 로직을 이해하는데 꽤 시간이 오래걸렸던 문제였다.

---

참고자료

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

[백준] 11050번 : 이항 계수 1 - JAVA [자바]

https://shoark7.github.io/programming/algorithm/3-ways-to-get-binomial-coefficients