[백준5568] / 카드 놓기 - 백트래킹

 

백준5568

 

푼 날짜 : 2024.12.10

푼 문제 : [5568] / 카드 놓기

사용한 언어 : python

알고리즘 : 백트래킹

 

 

 

접근방식 :

백트래킹 방식으로 하나씩 추가했다가 뺐다가 하는 방식으로 풀이했다.

이때 사용 유무를 확인하기 위해 visited배열을 선언하여 인덱스로 확인했을 때 사용한 카드라면 넘기고 사용하지 않은 카드를 확인하며 추가하도록 구현했다.

 

 

 

 

코드 :

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())

num_list = []
for _ in range(n):
    num = int(input())
    num_list.append(num)

# 카드 중복 사용을 체크하기 위한 배열
vistied = [0 for _ in range(n)]

# 중복 제거한 숫자 카드 조합을 저장하기 위한 set
mySet = set()

def backtracking(idx, new_num):
    global mySet, vistied
	
    # k개 만큼 놓았을 때 추가
    if idx == k:
        mySet.add(new_num)
        return 

    for i in range(n):
    	# 이미 사용한 카드라면 continue처리
        if vistied[i]: continue
        
        # 사용처리
        vistied[i] = 1
        # 현재 숫자의 길이
        now_len = len(str(num_list[i]))
        # 현재 숫자의 문자 변환
        now = str(num_list[i])
        new_num += now
        backtracking(idx+1, new_num)
        # 추가한 숫자의 길이만큼 문자열에서 제거하기 위함
        new_num = new_num[:-now_len]
        # 미사용 처리로 다시 변경
        vistied[i] = 0

backtracking(0, '')
print(len(mySet))

 

 

 

 

점점 늘고 있는 백트래킹 문제 풀이 실력~!~!~!~