[java 백준] 실버 2 / 1182번 부분수열의 합

https://www.acmicpc.net/problem/1182

import java.io.IOException;
import java.util.Scanner;
 
public class Main {
    public static int n, s;
    public static int[] arr;
    public static int ans = 0;
 
    public static void DFS(int i, int cnt) {
        if (i == n) { // 끝까지 돌았을 때
            return;
 
        } else {
            if (arr[i] + cnt == s) {
 
                ans++;
 
            }
 
            DFS(i + 1, cnt);// 지금꺼 넘어가기
            DFS(i + 1, cnt + arr[i]);// 지금꺼 더하기
 
        }
 
    }
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        s = sc.nextInt();
        arr = new int[n];
 
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
 
        DFS(0, 0);
        System.out.println(ans);
 
    }
 
}

이 문제는 백트래킹을 통해 풀어내는 문제였다. 그간 완전탐색을 풀면서 옆에 백트래킹이라고 써져있어서

굉장히 궁금했지만 귀찮아서 공부하지 않았던 나는 오늘 드디어 백트래킹에 대해 조금 공부해봤다.

 

백트래킹

현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘을 말한다.

 

수열이 예를 들어 -7,-3,-2,5,8이 있을 때 

부분 수열이라하면 -3,-2,5 / -7,5,8 등 굳이 수열이 연속될 필요없이 부분적으로 이어져 있는것이 이 문제가 원하는

부분수열이다.

https://www.youtube.com/watch?v=Enz2csssTCs 

 

 

이 강의에서 부분수열의 합을 설명하시는 부분에서 부분수열을 부분집합으로 치환해서 설명하셨는데 부분집합이라고 생각하면 문제가 굉장히 쉬워진다. 

문제에서는 -7,-3,-2,5,8의 부분수열의 합이 0이 되어야하는 경우의 수를 구하는 것이 의도이다. 

이 문제를 부분집합으로 생각하면 부분집합이 2^5,즉 32가 된다. 즉, 32개의 부분수열이 나오는 것이다. 부분집합의 합이 0이 되는 경우는 딱 한가지인데 {-3,-2,5}이다. 

 

이것을 재귀와 dfs를 통해 생각해보면 우선 0번째 인덱스인 -7부터 탐색한다. 

 

예를들어 {-3,-2,5,8} 이라는 부분집합이 있다면 첫번째 인덱스인 -7을 더해주지 않은 것이고

{-7,-2,-5,8}이라는 부분집합이 있다면 이는 첫번째 인덱스인 -7을 더해준것이다.

이것이 핵심이다. 부분집합을 구하고 싶으면 굳이 i번째 인덱스를 더하지 않고 패스해줘도 된다.

즉 i번째 인덱스를 더해주는 것은 부분집합에 원소를 추가하는 것과 같다. 

 

이걸 코드로 구현하면

DFS(i+1,cnt); //다음번 인덱스로 넘겨줄 뿐, 현재 인덱스에 해당하는 원소는 더하지 않음

DFS(i+1,cnt+arr[i]);//다음번 인덱스로도 넘겨주고 현재 인덱스에 해당하는 원소도 더해줌

 

dfs의 가장 큰 특징인 "끝까지 탐색"을 활용해 -> 만약 끝까지 탐색했다면 return 

만약 끝까지 탐색하지 않았는데 더한값이 s일지라도 -> 끝까지 탐색해준다.

 

여전히 백트래킹에 대해서는 확실히 모르겠지만 재귀를 사용해서 현재 상황에서 발생할 수 있는

모든 가짓수들을 고려해준다는 점은 알겠다.