[BAEKJOON/Python3] 백준 15651 N과 M (3)

www.acmicpc.net/problem/15651

15651번: N과 M (3)

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

N과 M이 주어졌을 때 1부터 N까지 자연수 중에서 M개를 고른 수열을 출력하고자 합니다. "같은 수를 여러번 골라도 된다"는 조건이 있기 때문에 N의 M승개의 정답이 나온다는 특징이 있습니다. 백트랙킹을 이용하여 해결할 수 있습니다. (N과 M(4)는 고른 수열이 비내림차순이어야 한다는 조건이 추가된 문제였습니다. jiwon.tistory.com/22 참고)

 

*백트랙킹(Backtracking Algorithm)은 순차적으로 해를 찾다가 해가 아닌 것 같으면 되돌아가서 해를 찾는 방법이라고 할 수 있습니다. 백트랙킹은 문제를 해결하며 해가 될 수 없는 부분은 아예 시도조차 하지 않는 것이라고 생각하면 되겠습니다. 대표적으로 미로탈출, N-queens 문제 등이 있습니다.

 

코드

 

N개의 수에서 M개를 골라야 하는 것이므로 개수를 이용하는 것이 편리하겠다고 생각했습니다.

count 숫자를 늘려가며 count가 M을 도달하면 현재까지 저장된 수들을 정답으로 출력하고 백트랙킹으로 돌아가는 방식입니다.

 

getAll 함수는 수열을 하나하나 구하기 위한 함수로, 이 함수에서는 밑에서 선언한 answer 리스트에 매번 답을 저장한 후 답이 완성되면 출력합니다. count 변수와 index 변수를 이용하는 함수이며 count는 위에서 언급했듯이 개수가 M이 될 때까지 증가하도록 수행되며, index는 0부터 순차적으로 진행되기 때문에 실제 수와는 1씩 차이가 나는 점을 고려해야 합니다.

중복된 수도 가능하고 순서도 상관없기 때문에 1부터 N까지 모든 수를 따져줍니다. 모든 수에 대하여 answer 배열에 문자열 형태로 넣어준 후 (나중에 출력할 때 join을 이용하기 위해) 재귀적으로 getAll 함수를 호출하여 count가 M을 도달할 때까지 진행된 후 돌아오도록 해주었습니다. 그리고 이 과정이 모두 마무리되면 answer에 넣었던 수들을 이용해 답을 모두 구한 것이므로 answer 리스트에서 다시 제거합니다.

 

이렇게 재귀적으로 하다보면 모든 수열을 구할 수 있게 됩니다.