[완전 탐색] 백준 5568번 (파이썬) : 카드 놓기

문제는 카드를 k장 골랐을 때 이를 나열하여 만들 수 있는 정수의 개수를 출력하는 문제이다. 당연히 중복은 제외된다.

from itertools import permutations

n, k = int(input()), int(input())
nums = []
result = set()
for i in range(n):
    num = input()
    nums.append(num)
    
for per in permutations(nums, k):
    result.add(''.join(per))
    
print(len(result))

고른 카드들을 경우의 수를 다 따라 알아봐야 하기 때문에 combination을 쓰면 되지 않냐고 할 수 있는데 조합은 (A, B)와 (B, A)를 같은 것으로 취급하지만 이 문제에서는 1과 2를 골랐다고 할 때 12과 21은 명확히 다르기 때문에 combination을 사용할 수 없다.

그래서 사용하는 것이 순열 함수 permutations이다. 순열 함수는 단순히 나열한 것 그대로를 받아들이기 때문에 사용한다.

 

먼저 for문을 통해 입력을 받아주고 다음에 permutations를 사용하여 숫자들을 경우의 수에 따라 섞은 다음 join을 통해 붙여서 하나의 수로 인식하게 한다.

그리고 set을 통해 중복을 제외한다.

 

permutations를 사용하지 않을거면 직접 만들어주는 방법도 있다.

def select(cnt):
    global string

    if cnt == k:
        result.add(string)
        return

    for i in range(n):
        if dp[i] == 0:
            dp[i] = 1

            tmp = str(card[i])
            string += tmp

            select(cnt + 1)

            dp[i] = 0
            string = string[:-len(tmp)]