BAEKJOON-15652 : N과 M (4)

BEAKJOON-1018 : N 과 M (4)

간단한 문제같지만 백트래킹에 아직 익숙하지 않은 난 간단하지 않은 문제였다.

처음엔 product를 이용해서 예외 처리하는 방식으로 풀었지만 메모리 초과로 인해 통과하지 못했다.

그제서야 백트래킹으로 풀 생각을 하기 시작했다.

문제를 푸는 데에 1시간이 넘었지만 이를 계기로 백트래킹에 대한 감을 잡을 수 있었다.

코드

def back(idx, n, r):
    global arr
    
    if idx == r:
        for i in arr:
            print(i, end=" ")
        print()
        return
    
    num = 1 if not idx else arr[idx-1]
    for i in range(num, n+1):
        arr[idx] = i
        back(idx + 1, n, r)

n, r = map(int,input().split())
arr = [0] * r
back(0,n,r)

n은 숫자의 최댓값, r(repeat)은 자릿수를 뜻한다.

숫자의 조합을 출력해줄 배열을 r 크기만큼 선언하고

0번째 인덱스부터 가지를 뻗기 시작한다.

num = 1 if not idx else arr[idx-1]
    for i in range(num, n+1):

이 코드를 보면 현재 인덱스에서 넣어질 숫자는 이전 인덱스의 숫자보다 작지 않은 수를 넣는다는 것을 알 수 있을 것이다.