[BOJ] 15652. N과 M (4)

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

15652번: N과 M (4)

 

 

1. 해결방법

"""
1. 아이디어
- 백트래킹 재귀함수 안에서, for문 돌면서 숫자 선택
- 배열의 첫 번째, 두 번째 숫자가 중복이 가능하기 때문에 방문기록을 할 필요가 없음
- 재귀함수에서 M개를 선택할 경우 print
- 비내림차순으로 출력해야 하므로 두 번째 숫자는 첫 번째 숫자보다 작으면 안되기 때문에 점차적으로 커져야함

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

3. 자료구조
- 재귀
- 배열 : 결과 int[]
"""

 

 

2. 정답코드

 

입력 예제(1)

3 1

출력 예제(1)

1
2
3

 

입력 예제(2)

4 2

출력 예제(2)

1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

 

입력 예제(3)

3 3

출력 예제(3)

1 1 1
1 1 2
1 1 3
1 2 2
1 2 3
1 3 3
2 2 2
2 2 3
2 3 3
3 3 3

 

코드

import sys
input = sys.stdin.readline

n, m = 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(i)
        recur(i)
        result.pop()


# main
recur(1)