[ BOJ ] 15664 : N과 M (10) ( SILVER 2 ) / Python

>> 문제 바로가기 (https://www.acmicpc.net/problem/15664)

문제

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

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

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

출력

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

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

풀이 과정

M개의 수를 고르는 백트래킹을 구현하되, 중복되는 수열을 출력하면 안 된다.

즉, 수열 1 2 2 3 에서 2개의 수를 고른다면 (1, 2) 나 (2, 3) 이 2번 출력되면 안 된다는 뜻이다.

( 1, 2 (2번째 인덱스의 2) ), ( 1, 2 (3번째 인덱스의 2) )

( 2 (2번째 인덱스의 2), 3 ), ( 2 (3번째 인덱스의 2), 3 )

 

중복되는 수열을 출력하지 않기 위해선, 이전에 내가 2를 선택하고 다음 수를 선택할 때, 또 같은 2를 선택하지 않게끔 구현하면 된다.

if (i != start and arr[i] != arr[i-1]) or (i == start):
    backtracking(now + [arr[i]], i+1)

K번째의 수를 선택하는 과정에서 이전에 고른 arr[i-1] 가 2이고, 이번에 고르려는 arr[i] 가 2 일때는 고르지 않아야 한다.

이를 위해, 맨 처음 배열을 정렬해주어야 한다.

사전 순으로 증가하는 순서로 출력하기 위해 start 매개 변수로 수 선택의 시작점을 정해주는 것도 잊지 말자.

 

import sys
input = sys.stdin.readline

n, m = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))
arr.sort()
def backtracking(now, start):
    if len(now) == m:
        print(' '.join(map(str, now)))
        return
    
    for i in range(start, len(arr)):
        if (i != start and arr[i] != arr[i-1]) or (i == start):
            backtracking(now + [arr[i]], i+1)

backtracking([], 0)