백준 | 1182번. 부분 수열의 합 - 백트래킹 (DFS) 문풀

⬛ 백준 1182번. 부분 수열의 합 - 백트래킹 (DFS) 문풀

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

---

💚 문제 접근 방식

• N개의 원소 각각에 대하여 1) 뽑는 경우 2) 뽑지 않는 경우 2가지의 가지치기가 가능하다.
• 시간복잡도는 O(2^n) 이고, N이 최대 20까지라서 시간 안에 해결할 수 있다.

[주의] 애초에 입력으로 S(타겟넘버)가 0으로 들어올 경우도 고려해주어야 한다. 이걸 고려안해주면 DFS는 호출되자마자 sum값이 S와 같아져서 count++처리를 해주기 때문이다.

• DFS는 깊이 N까지 모든 원소를 더할지, 더하지않을지 2갈래로 뻗으며 깊이 5까지 내려와서 완성된 부분수열의 합이 타겟 넘버와 같아질 경우에만 카운팅하면 되는 문제였다.
• 최근에 풀어본 적 있는 문제이다. 그때도 백트래킹(DFS)으로 해결했고, 자세한 풀이는 여기에 있다.

백준 | 1182번. 부분수열의 합 - 백트래킹, DFS 풀이

---

💚 제출 코드

import java.util.Scanner;

/**
 *  1182번. 부분 수열의 합 - 백트래킹 
 * @author MYLG
 *
 */
public class Main {
	static int N, S;
	static int[] arr;
	static int count= 0;
	//DFS
	static void DFS(int lv, int sum) {
		if(lv == N) {
			if(sum == S) {
				count++;
			}
			return;
		}
		
		DFS(lv+1, sum + arr[lv]); //현재 원소 선택 O
		DFS(lv+1, sum ); //선택 X
		
	}
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		N = kb.nextInt();
		S = kb.nextInt();//타겟 넘버
		
		arr = new int[N];
		for(int i=0; i<N; i++) arr[i] = kb.nextInt();
		
		DFS(0, 0);
		//애초에 0으로 들어온 경우는 DFS 돌자마자 ++처리 되므로 
		if(S == 0) count--;
		
		System.out.println(count);
	}
}