[Python] 15666 - N과 M (12)

[Silver II] N과 M (12) - 15666 

[문제 링크](https://www.acmicpc.net/problem/15666)

🗝️알고리즘 분류

• 백트래킹

---

💻문제 정의

자연수 N개가 주어졌을 때, 길이가 M인 수열을 모두 구하는 프로그램을 작성하는 문제이다.

이때 수를 여러번 사용하여 수열을 만들 수 있고, 비내림차순이어야 한다. 또한 수열은 중복되지 않는다.

 

 

💡접근 및 설계

백트래킹을 이용하여 문제를 해결할 수 있다.

수열은 비내림차순이어야 하기에 오름차순으로 정렬을 해준다. 또한 주어진 수를 여러번 사용할 수 있기에 중복 원소를 제거하고 수열을 만들때 여러번 사용할 수 있도록 한다.

 

백트래킹은 DFS로 구현할 수 있다. 빈 리스트를 생성하고 여기에 수를 하나씩 넣는다. 길이가 M을 만족한다면 해당 수열을 출력한 뒤 가장 마지막의 원소를 제거하고 그 다음 원소를 추가한다. 해당 과정을 함수의 재귀호출로 반복한다.

 

✏️알고리즘 풀이

seq = list(set(map(int, input().split()))) # set 중복 제거 수열 입력
seq.sort()

s = []
def dfs(x):
    if (len(s) == M):
        print(*s)
        return
    
    for i in range(x, len(seq)):
        s.append(seq[i])
        # print(f"현재 상태 : {s}")
        dfs(i)
        s.pop()

x는 0부터 시작한다.

 

seq[0]을 s에 넣고, dfs(0)을 호출, seq[0]을 s에 넣는다. 이 과정을 반복 하다가 len(s) == M을 만족하면 수열을 출력.

 

return에 의해 함수가 종료되고 s.pop()을 실행. 수열의 가장 마지막 원소 seq[0]은 제거된다. 이후 반복문을 통해 seq[1]가 s에 추가된다.

 

seq[1]이 추가됨가 동시에 len(s) == M을 만족하였기에 수열을 출력. return에 의해 함수가 종료되고 s.pop()을 실행. seq[2]가 s에 추가.

 

이후 과정 반복.

 

🗒️전체 코드

# 15666 N과 M (12)

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
seq = list(set(map(int, input().split()))) # set 중복 제거 수열 입력
seq.sort()

s = []
def dfs(x):
    if (len(s) == M):
        print(*s)
        return
    
    for i in range(x, len(seq)):
        s.append(seq[i])
        # print(f"현재 상태 : {s}")
        dfs(i)
        s.pop()

dfs(0)

---