[BOJ] 15663. N과 M (9)

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

15663번: N과 M (9)

 

 

1. 해결방법

"""
1. 아이디어
- 입력 리스트를 오름차순으로 리스트에 저장
- 백트래킹 for문 돌면서 해당 원소를 append
- 원소의 중복되는 수열 때문에, 이전 인덱스를 기억하고 선택하면 패스하도록 함
- 재귀에서 m개를 선택하면 종료, print

2. 시간복잡도
- N^N (N = 7) : 가능

3. 자료구조
- 배열 : 입력 int[]
- 백트래킹 : 재귀
"""

 

 

2. 정답코드

입력 예제(1)

3 1
4 4 2

출력 예제(1)

2
4

 

입력 예제(2)

4 2
9 7 9 1

출력 예제(2)

1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

입력 예제(3)

4 4
1 1 1 1

출력 예제(3)

1 1 1 1

 

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
number = sorted(list(map(int, input().split())))

result = []
chk = [False] * (n + 1)


# recur
def recur(num):
    # 재귀 종료 지점
    if num == m:
        print(' '.join(map(str, result)))
        return

    # 이전 원소 값 저장
    remember = 0
    # 재귀
    for i in range(0, n):
        if chk[i] == False and remember != number[i]:
            result.append(number[i])
            chk[i] = True
            remember = number[i]
            recur(num + 1)
            result.pop()
            chk[i] = False


# main
recur(0)

이때까지의 N과 M과는 좀 다르게 입력 원소에 중복된 값이 존재한다.

이러한 입력 리스트 중복된 원소를 제거하고 출력하기 위해서는 remember라는 변수를 하나 추가해주어야 한다.
변수에 해당 depth에서의 원소 값을 저장하고, 재귀를 돌리면 바로 remember 변수는 바로 직전 원소 값이 되는데 이 변수 값과 재귀를 돌린 변수 값이랑 비교해서 중복이면 pass하도록 if문을 설계하였다.