[백준/Python]15663: N과 M (9)

문제

https://www.acmicpc.net/problem/15663
백준 문제집 - 0x0C강 - 백트래킹

 

알고리즘: 백트래킹

---

풀이

- N개의 자연수 중에서 M개를 고른 수열
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

한 숫자를 중복선택할 순 없으나 같은 숫자가 여러개 주어질수도 있다.
예를들어 [1, 2, 4, 4]일때, 세번째의 4와 네번째의 4는 다른 4다.
단, 완성된 수열은 중복되어선 안된다.

 

사실 모든 숫자가 최대 하나씩만 주어진다면 15654: N과 M (5) 문제와 동일하다.
하지만 이번 문제도 if nums[i] in ret과 같이 작성하게 되면 [1, 2, 4, 4]처럼 '같은 숫자가 여러개 주어지는 경우'를 판별할 수 없다.

따라서 숫자 사용여부를 저장할 리스트, 이전에 사용한 숫자를 저장할 변수를 생성해줘야한다.

 

전체 코드

# 메모리: 31120KB / 시간: 68ms
from sys import stdin


input = stdin.readline

N, M = map(int, input().split())
nums = sorted(map(int, input().split()))
used = [False] * N

ret = []

def backtrack(ret):
    if len(ret) == M:
        print(" ".join(map(str, ret)))
        return

    curr = 0
    for i in range(N):
        # i번째 숫자를 사용하지 않았고 이전 숫자와 다른값이라면
        if not used[i] and curr != nums[i]:
            used[i] = True
            ret.append(nums[i])
            curr = nums[i]
            backtrack(ret)
            ret.pop()
            used[i] = False

backtrack([])

 

👇 아래는 좀 더 자세한 과정이

아까의 예시와 같이 [1, 2, 4, 4]가 주어졌고, 1이나 2로 시작하는 수열은 만들어둔 상태라고 가정해보자.
(N, M은 각각 4, 2로 가정)

# i가 2일때
	curr = nums[1] = 2
	used = [False, False, False, False]
	
	if not used[2] and curr != nums[i]:
	    used[2] = True
    	ret.append(nums[2])
    	curr = nums[2]
    	backtrack(ret)
	
	# 현재까지의 결과
	ret = [2]
	used = [False, False, True, False]
	curr = 4
	
	# backtrack(ret) 시작
	curr = 0 으로 초기화
	
	# i = 0
	used[0] = False, curr != nums[0] 이므로 ret = [4, 1] => print 후 pop(), curr은 nums[0]
	# i = 1
	used[1] = False, curr != nums[1] 이므로 ret = [4, 2] => print 후 pop(), curr은 nums[1]
	# i = 2
	used[2] = True 이므로 continue, curr은 변경없이 nums[1]
	# i = 3
	used[3] = False, curr != nums[3] 이므로 ret = [4, 4] => print 후 pop(), 순회가 끝났으므로 맨 처음 i = 2로 return
	
	다시 i = 2로 돌아와서 backtrack(ret)이 끝났으므로 pop(),
	ret = [], curr = nums[2]
	# i가 3일때
	used[3] = False 이지만 curr == nums[3]이므로 continue, 순회가 끝났으므로 모든 backtrack 함수 실행 종료