[BOJ] 15651번: N과 M (3)

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

 

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

 

풀이

완전탐색(백트래킹) 방식으로 문제를 해결하였다. (백트래킹의 전형적인 로직이라고 하니 잘 기억해두자!!!!)

* n이 작은 (< 20 정도?) 수라면 완전탐색을 고려해보기!!!

def go(arr):
    if len(arr) == M:
        print(' '.join(map(str, arr)))
        return
    for i in li:
        arr.append(i)
        go(arr)
        arr.pop()

N, M = map(int, input().split())
li = [i for i in range(1, N + 1)]
go([])

 

1. N, M을 입력받는다

2. li에 필요한 요소들(1~N)을 삽입한다.

3. 빈 리스트로 go 함수를 호출한다

4. (go 함수) 리스트 li에 대해 반복문을 수행하며, 파라미터 arr을 출력을 위한 반복문이라고 생각하면 된다.

5. arr에 요소가 M(출력할 길이)개 있다면, 그대로 출력한 후 return하여 그 전 함수호출로 되돌아간다.

6. 그렇지 않다면, arr에 삽입 -> 출력 후 pop을 반복한다.

 

 

이와 비슷한 백트래킹 문제 풀이를 보고싶다면 아래 링크를 들어가보세요!! 제가 저희 알고리즘 스터디 블로그에 쓴 글이랍니다.😎

https://kau-algorithm.tistory.com/1591