15667

날짜 : 2023. 10. 19

사용 언어 : python

 

문제

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

 

 

코드

import sys

def dfs(idx, nums):
    # print(type(nums))
    if len(nums) == m:
        for i in range(m):
            print(nums[i], end=" ")
        print()
        return
    before = -1
    for i in range(idx, n):
        if i == idx + 1: before = arr[idx]
        if before == arr[i]:
            continue
        nums.append(arr[i])
        dfs(i, nums)
        nums.pop()

n, m = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))
arr.sort()  # 오름차순 정렬
res = list()

dfs(0, res)

 

 

풀이

- 오름차순 정렬 후 백트래킹을 실행한다.

- 본인을 포함하여 수열을 만들 수 있고, 중복되지 않은 수열을 만들어야 하며, 오름차순으로 이루어져 있어야 한다.

- 중복을 제거하기 위해 이전에 선택했던 것과 다음에 선택했던 것 사이에서 continue 를 통해 겹치지 않게 구현하고 해당 케이스에 걸리지 않는 경우 전달하기 위한 리스트에 해당 인덱스 값을 넣어 DFS를 실행, 빠져나온 후에는 pop을 실행한다.

 

 

알게된 점

- 기본적인 백트래킹 문제였지만 곧바로 구현하는 데에는 살짝 시간이 소모되었다.

 

 

참고 사이트

-