(Python/🥈2)백준리즘알고리즘 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인 경우 둘째 줄은 주어지지 않는다.

 

출력:

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

 

풀이:

 

product 사용했지만 시간초과 나옴

import sys
from itertools import product
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int, input().split())
lst = list(map(int, sys.stdin.readline().split()))

num = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
count = 0

for i in product(num, repeat=n):
    if all(k in i for k in lst):
        count += 1

print(count)

 

2. 백트래킹 사용

 

import sys
from itertools import product
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

n, m = map(int, input().split())
lst = list(map(int, sys.stdin.readline().split()))


count = 0
def bt(res):
    global count
    if len(res) == n:
        for i in lst:
            if i not in res:
                break
        else:
            count +=1
        return

    for i in range(10):
        res.append(i)
        bt(res)
        res.pop()

for i in range(10):
    res = []
    res.append(i)
    bt(res)
    res.pop()
print(count)