[BAEKJOON/Python3] 백준 15656 N과 M (7)

www.acmicpc.net/problem/15656

15656번: N과 M (7)

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

 

백트랙킹을 이용해서 해결하는 N과 M 7번째 문제입니다. N개의 수 중에서 M개를 고르고 같은 것을 골라도 되며 중복되지 않게 사전 증가 순으로 출력합니다. N과 M (3) 과 비슷하지만 다른 점이 있다면 (3)은 4개중에서 선택이면 1,2,3,4 중에서 선택으로 해결하는 문제였다면 이 문제는 값들이 따로 주어진다는 것입니다. 방식은 같지만 사용할 수들을 입력받아 배열로 저장하고 오름차순으로 하여 그 인덱스를 활용해서 문제를 해결했습니다.

 

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

 

코드

 

백트랙킹을 이용할 (재귀적으로) 함수 findAll을 정의하였습니다.

count 변수를 이용해 M까지 모두 세었다면 정답 배열에 있는 값들을 문자열 형태로 변환한 뒤 공백으로 연결하여 출력한 후 함수를 종료하도록 했습니다. 그리고 M을 아직 도달하지 않았다면 0부터 N-1까지의 인덱스를 활용해 answer 배열에 순차적으로 넣고, 해당 수를 정답에 넣으면 count가 1이 증가하므로 이를 활용해 재귀적으로 findAll 함수를 호출했습니다. 이렇게 호출하면 그 수를 넣은 경우의 정답을 모두 찾은 뒤 돌아올 것이므로 가장 최근에 넣었던 값을 다시 제거하도록 pop을 해주었습니다.

이렇게 모든 경우에 대하여 정답을 구한 후 함수가 종료됩니다.

 

함수를 정의하고 N,M을 입력받아 정수형으로 변환하였고, N개의 수도 입력받아 정수형으로 변환하여 배열 A에 저장하고 오름차순으로 정렬하였습니다. answer는 정답을 구하기 위한 배열로 이용하였고 처음에는 비어있기 때문에 count를 0으로 하여 함수를 호출하도록 했습니다.