BaekJoon 6591, 이항 쇼다운 조합문제

조합의 수를 구하는 알고리즘을 짜면 되는 심플한 문제입니다.

https://www.acmicpc.net/problem/1011

일단 팩토리얼을 구해서 곱하고 나누고 하는 문제가 아니라, 중간 과정에서
나눠 주는 것이 포인트입니다.

안그러면 int 범위를 벗어나서 값이 이상해집니다.
저는 gcd를 이용해서 값을 나눠주면서 계산을 했습니다.

import java.io.*;

public class B6591 {
    static int N, M;
    static int[] a = new int[101];
    static int[] b = new int[101];
    static String in;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while (!(in = br.readLine()).equals("0 0")) {
            N = Integer.parseInt(in.split(" ")[0]);
            M = Integer.parseInt(in.split(" ")[1]);
            int topEnd, bottom;
            topEnd = (N - M > M) ? N - M : M;
            bottom = N - topEnd;
            for (int i = N; i > topEnd; i--) {
                a[N - i] = i;
            }
            for (int i = 1; i <= bottom; i++) {
                b[i - 1] = i;
            }

            for (int i = 0; i < bottom; i++) {
                for (int j = 0; j < N - topEnd; j++) {
                    int gcd = gcd(b[i], a[j]);
                    if (gcd > 1) {
                        a[j] /= gcd; b[i] /= gcd;
                    }
                }
            }
            long ans = 1;
            for (int i = 0; i < N - topEnd; i++) {
                if (a[i] == 0) break;
                ans *= a[i];
            }
            for (int i = 0; i < bottom; i++) {
                ans /= b[i];
            }
            bw.write(ans + "\n");
            bw.flush();
        }
        bw.close();
    }
    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }
        return Math.abs(a);
    }
}

이 블로그 검색

Do.

BaekJoon 6591, 이항 쇼다운 조합문제

이 블로그의 인기 게시물

웹툰 무료로 볼 수 있는 사이트

BackJoon 1011, Fly me to the alpha centauri, 규칙 찾기 문제