[BOJ] 15650. N과 M (2)

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

15650번: N과 M (2)

 

1. 해결방법

"""
1. 아이디어
- 백트래킹 재귀함수 안에서, for문 돌면서 숫자 선택 (방문여부 확인해야함)
- 재귀함수에서 M개를 선택할 경우 print
- [1, 2], [2, 1] 속성이 같은 경우에는 중복을 제거해야하므로 재귀 시작 범위를 +1씩

2. 시간복잡도
- N! : 가능 (문제의 N이 자연수 8까지)

3. 자료구조
- 방문 여부 : bool[][]
- 선택한 값 입력 배열 : int[]
"""

 

 

2. 정답코드

import sys
input = sys.stdin.readline


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

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


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

    # 재귀
    for i in range(num, n + 1):
        if chk[i] == False:
            chk[i] = True
            result.append(i)
            recur(i + 1)
            chk[i] = False
            result.pop()


# main
recur(1)

 

중복을 제거해야하기 때문에 시간이 좀 걸렸다.
왜 나만 어렵지..?

함수의 시작을 1로 했다. 그래야 함수 내의 재귀 for문 시작 범위를 1씩 증가시켜서 중복을 제외시킬 수 있었고, 재귀를 i+1로 설정해서 for문 시작지점보다 작은 숫자를 제외하면서 로직을 구형했다.