백준 15650번 N과 M (2) 리뷰

문제

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

입력

첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다.

출력

첫째 줄에 옮긴 횟수 K를 출력한다.
두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

기본적인 백트래킹 유형의 문제이다.

백준 N과 M(15649번 Permutation) 문제와 거의 동일한데 여기서는 수열이 오름차순이라는 조건이 붙는다.
백트래킹의 기본은 유먕하지 않으면 배제하는 것(Pruning) 이기 때문에 이 조건을 잘 짜야한다.
이 부분은 아래 코드 41번 줄에 구현하였다.

nums는 사용가능한 모든 수를 담는 배열인데, 중복을 허용하지 않기 때문에 List의 contains함수를 이용해 조건을 맞춰준다.
그리고 오름차순이기 때문에 temp에는 이전 값들 보다 큰 값이 들어가줘야하기 때문에 temp의 top보다 i가 커야만 실행될 수 있게 해준다.

전체 코드는 출력의 한 줄을 List에 담고 이 List들을 전체 하나의 List로 묶는 형식이다. (담는 조건은 List의 크기가 M과 같아질때!)