BOJ 1182번 <부분수열의 합>
난이도 :실버 2
알고리즘 분류 :백트래킹
굳이 따지고보면 난이도가 높지도 않지만 굳이 이 문제를 포스팅 하는 이유는 알고리즘 공부를 꾸준히 한지 아직 채 한달이 되지않은 나에게는 백트래킹의 재귀함수 동작과정이 익숙하지 않기 때문이다.
백준에서 백트래킹 대표 예제들로 꼽히는 N과 M 문제들을 힘겹게 풀었지만 며칠 뒤 다시 백트래킹 문제를 풀려고하니 제대로 기억이 나지 않았다. 작동과정을 자세히 서술하여 장기기억으로 가기 바라는 마음으로 포스팅을 시작한다.
우선 어이없게도 이 문제를 해결하는데 첫번째 걸림돌은 부분 수열의 정의 를 명확히 알지 못했다는 것이다. 모든 부분 수열의 경우를 따지라는 것은 결국 모든 오름차순 수열의 경우 를 구하는 것과 같다는 것을 알지 못했다. 20분쯤 씨름을 하고 나서야 뭔가 이상하다는 것을 알게되었고, 부분수열의 정의를 찾아보고는 이마를 탁 치고 말았다.
void dfs(int count, int index) {
if (count > N) {
return;
}
for (int i = index; i <= N; i++) {
if (!visit[i]) {
visit[i] = 1;
sum += map[i];
if (sum == S) {
cnt++;
}
// 원소 하나 삽입
dfs(count + 1, i + 1);
/* 중 요 하 다 */
// 원소 하나 제거
visit[i] = 0;
sum -= map[i];
}
}
}
이것이 문제의 정답을 가르는 핵심 코드다. 나는 재귀함수를 호출하는 dfs(count+1, i+1) 코드 자리에 dfs(count+1, index+1) 를 집어넣었고 정답은 나오지 않았다.
dfs(count+1, index+1) 의 경우 현재 기점이 아닌 최초 index 를 기점으로 함수가 작동하게 된다. i = index 로 초기화 된 후 i 의 값이 점점 증가하더라도 초기의 index 값을 기반으로 dfs() 를 호출하게 되는 것이다. 따라서 중복없는 오름차순을 만들어내기 위해서는 dfs(count+1, i+1) 를 호출해야한다.
그렇게 되면 현재기점의 인덱스 + 1 위치부터 다음 원소탐색이 시작되고 오름차순을 만들 수 있다.
