정수론. 이항정리 1

Jung In Lee·2022년 10월 20일
0

문제

간단한 조합문제이다. 고등학교때 배운 nCr = n! / (n - r)! * r! 을 이용하면 간단히 풀수있다.

해결방향성

팩토리얼을 이용하는데, 재귀로 풀수도있고 반복문으로 풀수도있다. 재귀로 처음에 풀어보았는데, 다시 복귀하는 과정이 있어, (전부 이전 팩토리얼을 계산하면서 복귀) 시간이 너무 오래걸렸다. (재귀의 단점). 따라서 반복문을 사용하였다.

코드

package numbertheorycombination;

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

public class Combination {
    // 반복문으로 구현 : 재귀는 나올때도 곱하면서 나와서 너무 비효율적
    public static int factorial(int n) {
        int fac = 1;
        for (int i = 2; i <= n; i++) {
            fac *= i;
        }
        return fac;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int result = factorial(N) / (factorial(N - K) * factorial(K));

        bw.write(String.valueOf(result));

        bw.flush();
        br.close();
        bw.close();
    }
}

깨달은점

팩토리얼의 시간단축을 노린다면 반복문을 사용하자.

profile
Spring Backend Developer

0개의 댓글