[BOJ] 16단계 조합론

1

15439

베라의 패션

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        System.out.println(n*(n-1));
    }
}

 

2

24723

녹색거탑

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int cnt = 1;
        for(int i = 0; i < n; i++) {
            cnt = cnt * 2;
        }
        System.out.println(cnt);
    }
}

*Math.pow(): 거듭 제곱 구하는 함수

 

3

10872

팩토리얼

팩토리얼: N개의 물건을 일렬로 나열하는 경우의 수

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        int result = 1;
        while(n > 0) {
            result *= n;
            n--;
        }
        System.out.print(result);
    }
}

 

4

11050

이항 계수 1

이항 계수(조합): N개의 물건 중 K개를 순서 없이 고르는 경우의 수

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] split = reader.readLine().split(" ");
        int N = Integer.parseInt(split[0]);
        int K = Integer.parseInt(split[1]);
        //nCr = n! / (n-r)!r!
        System.out.print(factorial(N) / (factorial(N-K) * factorial(K)));

    }

    public static int factorial(int n) {
        if(n == 1 || n == 0) {
            return 1;
        }
        return n * factorial(n-1);
    }
}

*factorial 함수에 재귀 이용

 

5

1010

다리 놓기

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

public class Main {

    private static final int MAX = 30;

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

        int[][] dp = generateDp();

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < T; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int N = Integer.parseInt(tokenizer.nextToken());
            int M = Integer.parseInt(tokenizer.nextToken());
            sb.append(dp[M][N]).append("\n");
        }
        System.out.print(sb);
    }

    private static int[][] generateDp() {
        int[][] dp = new int[MAX+1][MAX+1];

        //파스칼의 삼각형: nCr = n-1Cr-1 + n-1Cr
        for(int i = 0; i <= MAX; i++) {
            dp[i][0] = 1;
            dp[i][i] = 1;
            for(int j = 1; j < i; j++) {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
            }
        }
        return dp;
    }
}

*동적 계획법(Dynamic Programming): 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

*파스칼의 삼각형: 이항계수를 삼각형의 형태로 배열한 것

*조합 계산식 [ nCr = n! / (n-r)! r! ] 을 사용하면 현재 N과 M의 범위(N, M <= 30) 에서는 팩토리얼 값이 64비트를 넘어서기 때문에 위와 같은 방식으로 계산함