[코딩테스트] 백준 11050 자바

백준 11050

백준 11050 문제

해당 문제는 조합을 구하는 간단한 문제이며, nCk를 구해주면 된다.

조합의 구하는 점화식인 D[i][j] = D[i - 1][j - 1] + D[i - 1][j]를 사용하여 배열을 초기화 해주면 간단하게 풀 수 있다.

import java.util.*;

public class Boj11050 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] arr = new int[n + 1][n + 1];

        // 배열 초기화
        for (int i = 0; i <= n; i++) {
            arr[i][1] = i; // i개에서 i개를 선택하는 경우의 수는 i개
            arr[i][0] = 1; // i개에서 1개도 선택하지 않는 경우의 수는 1개
            arr[i][i] = 1; // i개에서 모두 선택하는 경우의 수는 1개
        }

        // 점화식으로 배열 완성
        for (int i = 3; i <= n; i++) {
            for (int j = 2; j < i; j++) {
                arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]; // 조합을 구하는 점화식
            }
        }

        System.out.println(arr[n][k]);
    }
}

풀이

1. 행과 열이 n + 1의 크기를 갖는 2차원 배열을 선언한다.
2. 배열을 초기화하는데 nC1 n개 중 한 개만 선택하는 경우의 수는 n이기 때문에 n으로 초기화한다. (코드에서는 n이 i이다. arr[i][1] = i)
3. nC0 n개 중 한 개도 선택하지 않는 경우의 수는 1이기 때문에 1로 초기화한다. (코드에서는 n이 i이다. arr[i][0] = 1)
4. nCn n개 중 n개를 선택하는 경우의 수는 1이기 때문에 1로 초기화한다. (코드에서는 n이 i이다. arr[i][i] = 1)
5. 이제 조합을 구하는 점화식인 arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j]를 활용하여 비어있는 배열을 완성해준다. (비어있는 배열이 3열 2행부터 이기 때문에 비어있는 부분만 초기화해주기 위해 i를 3, j를 2로 해놓고, j는 i보다 작을 때까지 반복해준다.)