[백준] 1359번 복권 (Baekjoon Problem 1359: Lotto)

문제 출처, 해설 출처

 

[문제 요약]

복권 광고

1부터 N개의 수 중 서로 다른 M개의 수를 고른다.

복권도 1부터 N개의 수 중 서로 다른 M개의 수를 고른다.

적어도 K개의 수가 같으면 당첨

 

[풀이]
우선 전체 경우의 수를 구해보자

N개중 M개의 수를 고르는 모든 경우: nCm

 

당첨되는 경우의 수를 구해보자

K개의 수가 같은 경우

뽑은 M개중 복권과 겹치는 K개의 수를 정하는 경우: mCk

정확히 K개만 겹치기 때문에 나머지 뽑지 않은 N-M개에 복권에는 있는 M-K개의 수가 들어가야 한다: n-mCm-k

 

Combination(M, K) * Combination(N-M, M-K) / Combination(N, M)

 

[유의할 점 # 1]

다만 문제에서 적어도 K개의 수가 같으면 당첨이기에

K+1개가 수가 같은 경우, ..., M개의 수가 같은 경우까지 다 생각해야한다

 

[유의할 점 #2]

또 하나 유의 할점은 N-M <= M-K인 경우인데

1C2같이 그냥 처리를 해주면 당연히 계산 되지 않으므로 문제가 있다

 

이 상황은 직관적으로 보면 항상 당첨이 되는 경우인데

예를 들어 N=4, M=3, K=1이라고 하면

4개의 수중 3개의 수를 뽑는데 복권과 적어도 1개 이상의 수가 겹칠 확률은 (필연적으로 2개 이상 겹치기에) 1임

 

K를 나눠서 생각하면 아래와 같다.

4개의 수중 3개를 뽑는데 적어도 2개 이상의 수는 항상 겹치기 때문에

K = 1인 (하나만 겹치는) 경우는 불가함

K = 2인 경우와 K = M = 3일때의 확률을 더하면 1이다.

 

그래서 N-M < M-K인 경우는 확률을 1로 처리해주었다.

 

[파이썬 3 코드]

# 순열 nPr = n!/(n-r)! (순서 상관 유)
# 조합 nCr = n!/(n-r)!r! (순서 상관 무)

# 전체 경우의 수 = nCm
# k를 뽑는 경우의 수 = mCk (nCk가 아님)

def comb(n, k):
    numer = 1
    denom = 1
    while k > 0:
        numer *= n
        n -= 1
        denom *= k
        k -= 1
    return numer/denom

if __name__ == "__main__":
    n, m, k = input().split(" ")
    n = int(n)
    m = int(m)
    k = int(k)

    # k개 뿐만 아니라 k+1 ... m개를 포함하는 경우까지 다 더해주어야 한다
    total_prob = 0
    while m >= k:
        if n-m < m-k:
            total_prob = 1
            break
        else:
            prob = comb(m, k) * comb(n-m, m-k) / comb(n, m)
            total_prob += prob
            k += 1

    print(total_prob)