CodeDrive

문제:

웅찬이는 근성이 대단한 도둑이다. 그래서 금고를 털 때, 모든 조합을 눌러본다. 예를 들어 비밀번호가 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)가 주어진다.

출력:

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

풀이방법:

 처음에는 dfs를 활용한 백트래킹 방법으로 풀었다가 시간초과가 발생했다. 다른 방법을 생각해보던 중 수학적으로 풀 수 있음을 알게 되었다.

 따라서 포함배제의 원리를 사용해서 이 문제를 푼다. 문제에서 주어지는 n과 m만을 사용해서 풀수 있다.

m개의 수를 반드시 포함하는 경우의 수를 구하기 위해서 전체 가능한 경우의 수에서 m개의 수를 포함하지 않는 경우의 수를 빼는 것으로 구한다. 즉 다음과 같다.

비밀번호에 들어가는 수 m을 반드시 포함하는 비밀번호의 수 = 전체 비밀번호의 수 - m개의 수가 포함되지 않은 비밀번호의 수

전체 경우의 수는 10^n가 된다. m개의 수가 포함되지 않은 비밀번호의 수는 포함배제의 원리를 사용해서 구하도록 한다. 즉 구하는 식은 다음과 같이 된다.

answer = 10^n - mC1*9^n+mC2*8^n-mC3*7^n+.....

문제링크:

www.acmicpc.net/problem/13908