[BOJ] 15651. N과 M (3)

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

15651번: N과 M (3)

 

 

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 1
2 2
2 3
2 4
3 1
3 2
3 3
3 4
4 1
4 2
4 3
4 4

 

코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())

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


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

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


# main
recur(0)

M과 N(1)과 비슷하지만 if 문을 제거하였다.
이유는 중복을 허용하기 때문이다.