15666

날짜 : 2023. 09. 30

사용 언어 : python

 

문제

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

 

 

코드

import sys

def bt(idx, path):
    if len(path) == m:
        if path not in res:
            res.append(path)
        return
    for i in range(idx, n):
        bt(i, path + [a[i]])
    return


n, m = map(int, sys.stdin.readline().split())
a = list(map(int, sys.stdin.readline().split()))
a.sort()
# print(a)

res = list()
bt(0, [])

res.sort()
for i in res:
    print(*i)

 

 

풀이

- 기본적인 백트래킹을 활용한 문제

- 조건에 따라 입력받은 후 해당 수들을 오름차손으로 정렬한다.

- 그 다음, 현재의 인덱스를 저장한 상태에서 DFS를 실행하고, 재귀를 진행하면서 수열의 길이가 M값과 동일한 경우 결과를 저장할 리스트에 해당 수열과 중복되는 지 확인 후 종복되지 않으면 추가한 다음 리턴한다.

- 기존에 중복이 발생한 경우에도 리턴하여 재귀를 탈출한다.

- 전부 재귀가 완료된 다음 각각의 수열을 출력한다.

 

 

알게된 점

- in을 활용해서 중복을 체크한 것은 m, n값이 작았던 것과 유효한 시간이 2초라서 가능했던 것 같다.

- 중복을 제거할 수 있는 다른 방법도 찾아봐야겠다.

 

 

참고 사이트

-