[BOJ/Python] 백준 15663, 15666 - N과 M(9), (12)

문제

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

n, m = map(int, input().split())
num = sorted(list(map(int, input().split())))
visited = [0] * n
# 방문 체크: 중복은 불가능하나 같은 수가 2개 이상 들어있다면
# [n,n] 출력이 필요함.. 리스트 단에서 중복 제거가 불가능함
def function():
    if len(ans) == m:
        # ans의 길이가 m과 같아지면, 현재까지 숫자 출력
        print(*ans)
        return
    chk = 0
    for i in range(n):
        if chk != num[i] and visited[i] == 0:
            ans.append(num[i])
            visited[i] = 1
            chk = num[i] # 포인터를 이동시킴
            function() # DFS로 계속 탐색
            # 재귀호출 후 이전 상태로 돌아감(백트래킹)
            # 새로운 조합 탐색
            ans.pop()
            visited[i] = 0

ans = []
function()

 

1. 수열을 만드는 과정에서 같은 수를 여러 번 사용할 수 없으므로 방문 리스트를 활용하였다.
2. n번째까지 모든 경우의 수를 다 돌기 위해 한 번 사이클을 돌 때마다 방문 리스트를 초기화하고, 마지막으로 추가된 인덱스를 제거한다.
3. 재귀호출을 들어갈 때마다, ans 배열과 길이 m을 비교하여 같은 경우 수를 바로바로 출력한다.

문제

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

 

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

풀이

n, m = map(int, input().split())
num = sorted(list(map(int, input().split())))
# 방문 체크: 중복은 불가능하나 같은 수가 2개 이상 들어있다면
# [n,n] 출력이 필요함.. 리스트 단에서 중복 제거가 불가능함
def function(start):
    if len(ans) == m:
        print(*ans)
        return
    chk = 0 # 중복 수열 제거
    for i in range(start, n):
        if chk != num[i]:
            ans.append(num[i])
            chk = num[i] # 포인터를 이동시킴
            function(i) # 다음 호출에서 현재 인덱스부터 시작
            ans.pop()

ans = []
function(0)

• 위와 동일한 풀이인데 같은 수를 여러 번 골라도 되는 경우이므로 방문 리스트만 제거하여 풀었다.