[BOJ] 15657. N과 M (8)

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

15657번: N과 M (8)

 

 

1. 해결방법

"""
1. 아이디어
- 입력 리스트를 오름차순으로 리스트에 저장
- 수열의 같은 원소의 중복을 허용하기 때문에 방문기록 x
- 결과 리스트에 담은 원소들은 오름차순이어야 함. -> 원소를 넣을 때마다 점차적으로 증가시켜줘야함.
- 백트래킹 for문 돌면서 해당 원소를 append
- 재귀에서 m개를 선택하면 종료, print

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

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

 

 

2. 정답코드

 

입력 예제(1)

3 1
4 5 2

출력 예제(1)

2
4
5

 

입력 예제(2)

4 2
9 8 7 1

출력 예제(2)

1 1
1 7
1 8
1 9
7 7
7 8
7 9
8 8
8 9
9 9

 

입력 예제(3)

4 4
1231 1232 1233 1234

출력 예제(3)

1231 1231 1231 1231
1231 1231 1231 1232
1231 1231 1231 1233
1231 1231 1231 1234
1231 1231 1232 1232
1231 1231 1232 1233
1231 1231 1232 1234
1231 1231 1233 1233
1231 1231 1233 1234
1231 1231 1234 1234
1231 1232 1232 1232
1231 1232 1232 1233
1231 1232 1232 1234
1231 1232 1233 1233
1231 1232 1233 1234
1231 1232 1234 1234
1231 1233 1233 1233
1231 1233 1233 1234
1231 1233 1234 1234
1231 1234 1234 1234
1232 1232 1232 1232
1232 1232 1232 1233
1232 1232 1232 1234
1232 1232 1233 1233
1232 1232 1233 1234
1232 1232 1234 1234
1232 1233 1233 1233
1232 1233 1233 1234
1232 1233 1234 1234
1232 1234 1234 1234
1233 1233 1233 1233
1233 1233 1233 1234
1233 1233 1234 1234
1233 1234 1234 1234
1234 1234 1234 1234

 

 

코드

import sys
input = sys.stdin.readline

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

result = []


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

    # 재귀
    for i in range(num, n + 1):
        result.append(number[i - 1])
        recur(i)
        result.pop()


# main
recur(1)