[BOJ] 1359 복권

문제 링크

www.acmicpc.net/problem/1359

풀이

비트가 M개 켜지는 모든 경우에 대해 $2^M-1$과 겹치는 비트가 K개 이상인 경우의 수를 구해주면 된다.

Java 코드

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

public class Main {
    public static int bitCnt(int n) {
        int ret = 0;
        for (; n > 0; n -= n & -n) ret++;
        return ret;
    }
    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 M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        int bit = (1 << M) - 1;
        int a = 0, b = 0;
        for (int i = 1; i < 1 << N; ++i) {
            if (bitCnt(i) != M) continue;
            ++b;
            if (bitCnt(bit & i) >= K) ++a;
        }

        System.out.printf("%.15f", (double)a / b);
    }
}