[백준 13908번] : 비밀번호 파이썬 풀이

비밀번호 

1 초

64 MB

2081

786

605

43.525%

문제

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

출력

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

예제 입력 1 복사

2 1
7

예제 출력 1 복사

19

예제 입력 2 복사

2 2
3 4

예제 출력 2 복사

2

힌트

첫 번째 예제의 경우 가능한 비밀번호의 조합은 07, 17, 27, 37, 47, 57, 67, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 87, 97이다. 두 번째 예제의 경우 가능한 비밀번호의 조합은 34, 43이다.

 

처음 문제를 접근했던 방식은 '선견지명'으로 알고 있는 숫자들을 미리 배치한 뒤, 남은 숫자들을 배치하는 것이었다.

하지만 위 방법으로 접근하게되면 알고리즘이 지나치게 복잡하게 된다는 단점이 있었고 생각을 단순화하여 수를 배치한 뒤 '선견지명'으로 알고있는 숫자들을 포함하는지 확인하는 방식으로 방향을 틀었다.

 

숫자들을 중복으로 포함할수 있기 때문에, '중복 순열'을 사용해야 하며 파이썬은 itertools의 product를 사용하여 이를 쉽게 구현 할 수 있다.

 

위 아이디어를 적용한 코드는 아래와 같다.

# https://www.acmicpc.net/problem/13908
from itertools import product  # 중복 순열
'''
중복 순열을 이용하여 만들 수 있는 모든 숫자를 만들어보고
만들어진 숫자가 '이미 알고 있는 수'를 포함한다면 result +=1
'''
result = 0
numbers = [i for i in range(10)]
n, m = map(int, input().split())
if m == 0:
    known = []
else:
    known = list(map(int, input().split()))  # 이미 알고 있는 수

for number_array in product(numbers, repeat=n):  # n개의 수 뽑기
    # 만들어진 수가 known을 모두 포함하는지 확인
    error = False
    for number in known:
        # 뽑은 숫자 배열에 known의 모든 수가 포함되어 있는지 확인
        if number not in number_array:  # 포함되어 있지 않다면
            error = True
            break
    if not error:  # 문제없이 known의 모든 수를 포함하였다면
        result += 1


print(result)

 

위 문제에서 주의해야 할 점은 m이 0으로 주어지는 경우, 알고있는 수에 대한 입력이 없다는 점이다. 

조건식을 통해 m이 0인 경우 빈 배열로 처리해야 하며, 수를 만든 이후, 수를 하나씩 비교하면서 '이미 알고있는 수'의 숫자가 모두 만들어진 수에 포함되는지 boolean 변수를 통해 확인하고 문제없다면 result를 +1 한다.

 

https://www.acmicpc.net/problem/13908

13908번: 비밀번호