[Python/파이썬] 백준 13908번 비밀번호

 

13908번: 비밀번호

 

문제

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 3글자 라는 사실을 알 때, 000, 001, 002, 003, … 998, 999의 모든 조합을 눌러본다. 그러나 웅찬이는 선견지명이 있어서 비밀번호에 어떤 숫자가 들어가는지 일부 알 수 있다. 예를 들어 3글자 비밀번호에 0이 들어감을 안다면 999 와 같이 0이 들어가지 않는 수는 가능성이 없다. 그러나 000, 012, 030과 같은 수는 가능하다. 비밀번호의 길이와 선견지명으로 알게된 비밀번호의 일부 숫자가 주어질 때, 모든 가능한 비밀번호의 개수를 출력하는 프로그램을 작성하시오.

입력

첫줄에 비밀번호의 길이 n (1 ≤ n ≤ 7), 선견지명으로 알게된 비밀번호에 들어가는 수 m(0 ≤ m ≤ n) 이 주어지고, 둘째 줄에 m개의 서로 다른 숫자(0~9)가 주어진다. m이 0인 경우 둘째 줄은 주어지지 않는다.

출력

가능한 모든 비밀번호의 개수를 출력한다.

코드

from math import factorial

n, m = map(int, input().split())
if m > 0:
    nums = list(map(int, input().split()))
else:
    print(10**n)
    exit()

# 포함배제의 원리
# 전체 경우의 수 - (선견지명 수를 포함하지 않고 만들기)
total = 10 ** n # 전체 경우의 수
tmp = 0
for i in range(1, m+1):
    tmp += ((-1)**(i-1)) * ((10-i) ** n) * (factorial(m)//(factorial(i)*factorial(m-i)))
print(total-tmp)

 

포함배제의 원리를 이용하여 풀이하였다.

포함·배제의 원리 - 나무위키