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

Soorim Yoon·2022년 9월 23일

알고리즘 & 코딩테스트

목록 보기

24/67

문제

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)))을 통해 리스트로 저장하려 해도 저장되지 않는다. (해당 값을 리턴할 수 있는 방법이 없는지 더 찾아봐야겠다.)