백준 15650: N과 M(2) (JAVA) <백트래킹 알고리즘 응용>

 

문제 해석

 

이전에 백트래킹 알고리즘으로 푼 N과 M 문제에서 오름차순인 수열만 골라내는 조건이 추가된 문제이다.

 

알고리즘

 

이전에 사용한 백트래킹과 유사한 형태이지만 함수에 인자로 깊이 뿐만 아니라 시작 위치도 인자로 주어야할 필요가 있다.

 

코드

 

resolve 함수의 인자로 idx(시작 위치 지정)을 추가하였다.

재귀호출을 하는 반복문에서 i의 시작조건을 이전처럼 0이 아닌 idx로 지정하였고

재귀호출시 i+1을 idx 인자로 전달하여 본인보다 큰 숫자에 대해서만 탐색하게 하였다.

1부터 시작하기에 초기 idx는 1로 한다. -> resolve(1, 0)

 

N이 4이고 M이 2인 경우

재귀호출을 하는 반복문 진행 순서를 보면

 

1차 호출: i=1 / result[0]=1 / resolve(2, 1) 

2차 호출: i=2 / result[1]=2 / resolve(3, 2) -> {1, 2} 출력 resolve(3, 2) 종료

2차 호출: i=3 / result[1]=3 / resolve(4, 2) -> {1, 3} 출력 resolve(4, 2) 종료

2차 호출: i=4 / result[1]=4 / resolve(5, 2) -> {1, 4} 출력 resolve(5, 2) 종료

1차 호출: i=2 / result[0]=2 / resolve(3, 1) 

2차 호출: i=3 / result[1]=3 / resolve(4, 2) -> {2, 3} 출력 resolve(4, 2) 종료

 

이전 문제같이 (1, 2, 3, 4) / (1, 2, 4, 3) 같은 경우는 고려할 필요가 없다.

따라서 이전 문제같이 한정조건을 방문여부로 하는 것이 아닌 idx를 한정조건으로 사용했다.