[파이썬] 백준 5568 카드 놓기

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

5568번: 카드 놓기

 

상근이가 만드는 순서가 상관 있기 때문에

순열 조합 중에서 순열으로 풀어야 한다.

또한, 같은 카드를 두번 고를 수는 없기 때문에, 중복이 아닌 순열으로 풀어야 한다.

 

n = int(input())
k = int(input())
arr = []
for _ in range(n):
    number = int(input())
    arr.append(number)
# print(arr)
path = [0]*(k+1)
used = [0]*len(arr)
check = []

전체 카드 수, 선택할 카드 수, 그리고 카드에 쓰여있는 수를 배열로 입력받는다.

  그 다음

1. 내가 선택한 카드들을 담는 리스트인 path

2. 내가 사용한 카드들을 체크하는 용도인 used

3. 내가 만든 숫자가 중복인지 아닌지 확인하는 check를 새롭게 만든다.

 

 

def rcr(level):

    if level == k:
        word = ''
        for i in path:
            word +=str(i)

        if word not in check:
            check.append(word)

        return

    for i in range(len(arr)):
        if used[i] ==0:
            used[i] = 1
            path[level] = arr[i]
            rcr(level+1)
            used[i] = 0

rcr(0)

<if 문>

level이 k 일때, 초기화 된 word라는 변수에 path에 있는 숫자들 이어붙힌거를 넣고,

 그 word가 check라는 리스트에 존재하지 않는다면 append해준다.

(즉, 이미 만들어진 숫자가 아닌 경우에만 check 리스트에 들어가게 된다)

 

<for문>

arr 전체를 돌면서, used가 0이면 (아직 이 카드를 사용한 적이 없으면)

사용했다는 표시를 해주고,

path에 arr[i]를 넣어준다.

그리고 다음 level으로 진입한다.

함수가 재귀에서 빠져나올때는 used를 다시 초기화시켜야 하기 때문에 그 아래에 used[i] = 0코드를 추가해준다.

 

 

 

 

 

전체 코드)

n = int(input())
k = int(input())
arr = []
for _ in range(n):
    number = int(input())
    arr.append(number)
# print(arr)
path = [0]*(k+1)
used = [0]*len(arr)
check = []
def rcr(level):

    if level == k:
        word = ''
        for i in path:
            word +=str(i)

        if word not in check:
            check.append(word)

        return

    for i in range(len(arr)):
        if used[i] ==0:
            used[i] = 1
            path[level] = arr[i]
            rcr(level+1)
            used[i] = 0

rcr(0)

print(len(check))