[백준 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)가 주어진다.

 

출력

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

---

접근

다른 사람들의 풀이를 보니 "포함배제의 원리"를 활용하였다.

N개의 수로 만들 수 있는 경우의 수 - M개를 포함하지 않고 만들 수 있는 경우의 수를 통해 빠른 시간 안에 구할 수 있었다.

 

하지만 나는 이를 알지 못하였고, 모든 경우의 수를 구하여 M개의 수가 포함되었는지 여부를 판단하였다.

 

구현

- 0부터 9까지의 수를 차례대로 picked라는 리스트에 넣고 solve함수에서 dfs를 실행한다.

for n in range(10):
    picked = []
    picked.append(n)
    solve(picked)
    picked.pop()

- 현재 picked의 길이가 N이라면 반드시 포함되어야하는 수가 picked에 모두 존재하는지 검사한다.

- 모두 존재한다면 최종해를 증가시킨다.

- 수를 선택할 때는 중복으로 선택할 수 있기 때문에 for문을 통해 0부터 9까지 선택할 수 있도록 하였다.

def solve(picked):
    global answer
    if len(picked) == N:
        for n in include_numbers:
            if n not in picked:
                break
        else:
            answer += 1
        return

    for n in range(10):
        picked.append(n)
        solve(picked)
        picked.pop()

---

전체 코드

import sys
input = sys.stdin.readline

def solve(picked):
    global answer
    if len(picked) == N:
        for n in include_numbers:
            if n not in picked:
                break
        else:
            answer += 1
        return

    for n in range(10):
        picked.append(n)
        solve(picked)
        picked.pop()

N, M = map(int, input().split())
include_numbers = list(map(int, input().split()))
numbers = [n for n in range(10)]

answer = 0
for n in range(10):
    picked = []
    picked.append(n)
    solve(picked)
    picked.pop()
print(answer)