백준 / 복권 / 1359번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 복권 / 1359번 (실버 4단계)

문제 사이트: https://www.acmicpc.net/problem/1359

 

문제 설명

---

나의 풀이

# 틀린 코드
# 조합을 고려하지 않았음 중복되어 계산하는 경우 발생!
# total = len(p1) * len(p2)가 맞음

def dfs(p, path, start, s, n):
    # 길이가 s이면 결과 리스트에 추가 후 종료
    if len(path) == s:
        p.append(path[:])  # 깊은 복사 후 저장
        return

    for i in range(start, n + 1):  # 오름차순 유지
        dfs(p, path + [i], i + 1, s, n)  # i+1부터 탐색하여 중복 방지


def solution(n, s, k):
    # 첫 번째 사람이 고르는 수
    p1 = []
    dfs(p1, [], 1, s, n)

    # 두 번째 사람도 같은 조합을 공유
    p2 = p1[:]  # 같은 조합을 사용

    # 모든 경우의 수
    total = len(p1) * len(p2)

    # 당첨 확률
    goal = 0

    # 공통되는 원소를 찾는 함수
    for i in range(len(p1)):
        for j in range(i, len(p2)):  # 중복 계산 방지
            common_elements = set(p1[i]) & set(p2[j])
            if len(common_elements) >= k:
                goal += 1

    # 확률 계산
    answer = goal / total if total > 0 else 0

    return answer


def main():
    # 정수의 개수를 나타내는 n, 정수 s, 최소 공통 원소 k
    n, s, k = map(int, input().split())

    print(solution(n, s, k))


if __name__ == "__main__":
    main()

위 풀이는 조합의 성질을 이용하지 않고 dfs를 이용하여 풀이를 하다보니 생각했던 논리적 계산과 차이가 나서 틀리게 된 것 같습니다!

# 정답 코드!
import math


def lottery_probability(N, M, K):
    total_cases = math.comb(N, M)  # 전체 조합의 개수
    win_cases = 0  # 당첨될 경우의 수

    # 공통되는 개수 X가 K 이상일 경우를 계산
    for x in range(K, M + 1):
        if N - M < M - x:  # 조합이 불가능한 경우 제외
            continue
        win_cases += math.comb(M, x) * math.comb(N - M, M - x)

    # 확률 계산
    return win_cases / total_cases if total_cases > 0 else 0.0


def main():
    # 입력 받기
    n, m, k = map(int, input().split())

    # 결과 출력
    print(lottery_probability(n, m, k))


if __name__=="__main__":
    main()

math함수를 이용하면 더 쉽고 빠르게 처리할 수 있습니다!

---

※ 알아야 할 것

파이썬의 내장된 함수를 사용하면 쉽게 해결할 수 있습니다!

def factorial(n):
    """ 팩토리얼 계산 """
    if n == 0 or n == 1:
        return 1
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

def comb(n, r):
    """ 조합 계산 """
    if r > n:
        return 0
    return factorial(n) // (factorial(r) * factorial(n - r))

위 코드는 조합을 직접 구현한 코드입니다!