[n5568] 카드 놓기 in python

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

5568번: 카드 놓기

---

(처음 든 생각)

이건 완탐으로 풀어야하는 것 같긴 한데..

수가 커질수록 경우의 수가 많아지고 ㅠㅠ

이럴 땐 어떻게 해야 할 지 모르겠다

일단 완탐으로 풀어보자!

 

n개의 카드 중에 k개를 선택하는 경우의 수를

다 써봐도 규칙이 보이지 않았다 ㅠㅠ

 

그래서 결국 인터넷 참고!

 

---

(풀이 : itertools 라이브러리)

n개의 카드 중에 k개를 선택하는 거 > 순열!

순열을 떠올리지 못했다.

떠올렸더라도 permutations를 사용해본 적이 별로 없어서

풀지 못했던 문제

 

지금이라도 익혀두자!

 

set() 사용법은 다행히 떠올렸었음!

중복이 있으면 안될때 유용하게 사용할 수 있기 때문!

 

* 순열 : permutation(list, n)

* 조합 : combination(list, n)

import sys
from itertools import permutations

n = int(sys.stdin.readline().rstrip())
k = int(sys.stdin.readline().rstrip())
cards_array = [sys.stdin.readline().rstrip() for _ in range(n)]
array = set()

for i in permutations(cards_array,k): #n개의 카드 중 k개를 선택하는 순열
    array.add(''.join(i))

print(len(array))

---

(순열 구현, 라이브러리 x, 재귀함수)

import sys

n = int(sys.stdin.readline().rstrip())
k = int(sys.stdin.readline().rstrip())
cards_array = [sys.stdin.readline().rstrip() for _ in range(n)]
array=set()

def permutation(cnt, perm, visit):
    global cards_array
    if cnt==k:
        array.add(''.join(perm))
        return
    for idx in range(n):
        if not visit[idx]:
            visit[idx]=1
            permutation(cnt+1,perm+[cards_array[idx]],visit)
            visit[idx]=0


permutation(0,[],[0]*n)
print(len(array))