문제 출처: https://www.acmicpc.net/problem/1359
문제
어제, 지민이는 몰래 리조트에 갔다가 입구에 걸려있는 복권 광고를 하나 보았다.
“1부터 N까지의 수 중에 서로 다른 M개의 수를 골라보세요. 저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다.!”
지민이는 돌아오면서 자신이 복권에 당첨될 확률이 궁금해졌다.
지민이가 복권에 당첨될 확률을 구하는 프로그램을 작성하시오.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static int[] nums;
private static int N, M, K;
private static List<String> lottoList = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
N = Integer.parseInt(tokenizer.nextToken());
M = Integer.parseInt(tokenizer.nextToken());
K = Integer.parseInt(tokenizer.nextToken());
nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = i + 1;
}
combination(0, 0, new StringBuilder());
int size = lottoList.size();
int totalCnt = 0;
for (String temp : lottoList) {
for (String s : lottoList) {
int cnt = 0;
for (int k = 0; k < M; k++) {
if (s.contains(temp.charAt(k) + "")) cnt++;
}
if (cnt >= K) totalCnt++;
}
}
System.out.println((double) totalCnt / (size * size));
}
private static void combination(int start, int cnt, StringBuilder sb) {
if (cnt == M) {
lottoList.add(sb.toString());
return;
}
for (int i = start; i < N; i++) {
int temp = sb.length();
sb.append(nums[i]);
combination(i + 1, cnt + 1, sb);
sb.setLength(temp);
}
}
}