[백트래킹] N과 M(3) (BO 15651번, 실버3)

문제

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

백준 백트래킹 문제로 <N과 M> 시리즈가 있다. <N과 M> 시리즈는 1부터 N까지의 숫자를 활용해 길이 M인 수열을 출력하는 문제이다. <N과 M(3)>은 1부터 N까지의 숫자를 중복해서, 순서는 숫자의 크기에 상관 없이 출력 가능하다.

• 1~N까지의 숫자를 중복하여 크기에 상관 없이 조합 가능한 길이 M의 수열을 모두 출력해라.

풀이

백트래킹 개념을 사용한다.

• 정답을 저장할 answer 배열을 생성하여 1부터 N까지의 숫자를 append 한다.
• 숫자 배열의 길이가 M과 같아지면 해당 배열에 저장된 값을 출력한다.
• 재귀 함수를 통해 배열에 값을 삽입하고 빼내는 과정을 반복한다.
• 배열에 가장 최근에 들어온 값을 빼고, 해당 자리에 값을 추가하는 과정을 반복하며 (1, 1, 1) (1, 1, 2) (1, 1, 3) 등 조합 가능한 모든 수열을 구한다.

코드

# N과 M (3)
# 수열을 구할 때, 같은 수를 여러 번 골라도 된다.

N, M = map(int, input().split())
answer = []

def back():
    if len(answer) == M:
        print(" ".join(map(str, answer)))
        return              # 리턴 값이 없더라도, 함수에서 return문이 없으면 오류 발생하므로 꼭 있어야 한다

    for i in range(1, N+1):
        answer.append(i)
        back()
        answer.pop()

back()

💡 알게된 점

• 함수 안에는 리턴 값이 없더라도 꼭 return 문을 써줘야 오류가 발생하지 않는다.
• " ".joint(map(str, answer)) 은 해당 값을 문자에 담더라도 return 할 수 없다. list(" ".join(map(str, answer)))을 통해 리스트로 저장하려 해도 저장되지 않는다. (해당 값을 리턴할 수 있는 방법이 없는지 더 찾아봐야겠다.)

출력

test 1)

입력 : 3 3

출력

test 2)

입력 : 3 1

출력