[알고리즘] 백준 5568 파이썬 - 카드 놓기

 

5568번: 카드 놓기

문제

상근이는 카드 n(4 ≤ n ≤ 10)장을 바닥에 나란히 놓고 놀고있다. 각 카드에는 1이상 99이하의 정수가 적혀져 있다. 상근이는 이 카드 중에서 k(2 ≤ k ≤ 4)장을 선택하고, 가로로 나란히 정수를 만들기로 했다. 상근이가 만들 수 있는 정수는 모두 몇 가지일까?

예를 들어, 카드가 5장 있고, 카드에 쓰여 있는 수가 1, 2, 3, 13, 21라고 하자. 여기서 3장을 선택해서 정수를 만들려고 한다. 2, 1, 13을 순서대로 나열하면 정수 2113을 만들 수 있다. 또, 21, 1, 3을 순서대로 나열하면 2113을 만들 수 있다. 이렇게 한 정수를 만드는 조합이 여러 가지 일 수 있다.

n장의 카드에 적힌 숫자가 주어졌을 때, 그 중에서 k개를 선택해서 만들 수 있는 정수의 개수를 구하는 프로그램을 작성하시오.

 

문제풀이

#01
def permutation(tmp,k):
    result=[]
    if k>len(tmp):
        return result
    if k==1:
        for i in tmp:
            result.append(i)
    elif n>1:
        for i in range(len(tmp)):
            ans=[i for i in tmp]
            ans.remove(tmp[i])
            for j in permutation(ans,k-1):
                result.append(tmp[i]+j)
    return result
#02
n=int(input())
k=int(input())
tmp=[input() for _ in range(n)]
tmp.sort()
#03
res=set(permutation(tmp,k))
print(len(res))

- #01 : 순열을 의미하는 함수이다. 라이브러리를 통해서 한 줄로 구현할 수 있지만 

           함수로 구현해보았다.

- #02 : n,k와 tmp를 입력받는다. tmp는 오름차순 정렬한다.

- #03 : 순열 함수에 tmp와 k를 입력하고 결과는 중복없이 res에 저장한다. res의 길이를 출력한다.