[ALGO#16] 백준 1182_실버2_부분 수열의 합 : DFS [JAVA]

 

 

문제 링크

1182번: 부분수열의 합

 

접근법

DFS로 원소를 넣는 경우와 넣지 않는 경우를 탐색한다. (조합)

DFS로 탐색하면서 입력 개수에 도달하면 원하는 답인지 확인한다. 이렇게 안하고 매 순간마다 if(sum== answer)을 확인하면 return구분이 복잡해진다. 또한 dfs 탐색으로 깊이를 끝까지 탐색해야 이 문제에서 완전 탐색으로 답을 구할 수 있다. 

private static void dfs(int idx, int sum) {
        // dfs로 돌며 누적시키다가 위치를 나타내는 v이 마지막 위치로 오면 원하는 값인지 아닌지 체크하여 count
			if(idx ==N) {
				// 합이 정답과 같을 때 
				if(sum == answer) {
				count++;
				}
				return;
			}
				// 현재 값을 포함 시킬 때 순열
				dfs(idx+1, sum+arr[idx]);
				// 현재 값을 포함 안 시킬 때 순열
				dfs(idx+1, sum);			
		}

 

 

 

DFS

dfs(depth + 1, sum + num[depth]);
dfs(depth + 1, sum);

dfs 탐색(조합)으로 일반적인 트리의 전위 순회 방식으로 탐색 순서를 파악했다. 또한 위에서 강조한 것 처럼 중간에 원하는 값이 나왔다고 해서 return 시키면 dfs로 완전 탐색을 못할 수 있다. 입력의 개수에 도달하고 나서 정답을 확인해야 한다. 

 

탈출조건인 index==n이 되지않으면 해당 index의 경우를 포함하든지 안포함하든지로 나눠 재귀를 돌게됩니다.

 

 

시간복잡도 : O(2^N)

 시간 제한이 2초로 주어졌는데, 수열의 길이인 N의 최댓값이 20이다. 각 원소를 합에 포함할 지, 하지 않을지 두 가지 선택지를 모든 원소에서 탐색한다고 하면 2^20 == 1048576 이다. 모든 경우의 수를 탐색해도 시간 제한 2초에 충분하게 풀어낼 수 있다.

 

 

주의

부분 수열은 양의 크기만 된다고 문제에서 적혀져 있으므로 공집합이 되는 경우만 제외시켜준다. 공집합이 나오는 경우는 입력 합이 0일 때이다. 이때만 count 개수를 1 뺴준다.

System.out.println(S == 0 ? ans - 1 : ans);

 

다른 방법으로는 DFS에서 cnt 변수를 두어 원소 개수가 1개 이상 일때만 정답 count를 늘리면 된다.

static void dfs(int idx, int sum, int cnt) {
		if(idx == N ) { 
			if(cnt > 0 && sum == M) { //cnt변수는 주어진 부분수열의 합(M)이 '0'인 경우 공집합을 제외시켜주기 위함
				result++;
			}
			return;
		}

		dfs(idx+1, sum + array[idx], cnt+1);
		dfs(idx+1, sum, cnt);
	}

 

 

 

회고

처음에 백트레킹을 잘못 걸어줘서 시간이 소비했다. if(cnt==N)으로 짜야하는데 원리를 다시 이해했다.
우선 백트래킹의 개념으로 접근하기 때문에, dfs 함수 내에서 카운트를 증가시키는 시점을 if(index == N)을 반드시 걸어주어야 한다. 만약 그렇지 않으면 dfs가 수열의 마지막 원소까지 접근하는데, 탐색 중간에 현재 인덱스에서 원소를 합에 포함하지 않고 다음 인덱스의 dfs를 호출하면 sum이 같은 값인데도 cnt증가가 반복적으로 발생하는 문제가 있다. 마지막 원소까지 모두 탐색이 완료된 후에 합을 계산해보고 cnt를 증가시켜주어야 한다.

cnt 가 N에 도달하기 전에 sum이 answer와 같해진다고해서 return시키면 안된다. 그럼 위에서 탐색 트리가 중간에 가위로 자른셈이 되어버린다(완전 탐색을 못한다)
dfs의 가장 큰 특징인 "끝까지 탐색"을 활용해 -> 만약 끝까지 탐색했다면 return 
만약 끝까지 탐색하지 않았는데 더한값이 s일지라도 -> 끝까지 탐색해준다.

if (cnt > N ) return;
		
		// 합이 정답과 같을 때 
		if(sum == answer) {
			count++;
			// 다음 요소가 0이 있는 경우 여기서 return 시키면 세지 못한다
			//return;
		}

 

성능 요약

메모리: 14208 KB, 시간: 132 ms

분류 : 백트래킹(backtracking), 브루트포스 알고리즘(bruteforcing)

 

전체 코드 (JAVA)

import java.io.*;
	import java.util.*;

	public class BOJ_S2_1182_부분수열의합_sol {
		static int answer;
		static int N;
		static int count;
		static int[] arr;
		
		public static void main(String[] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			StringTokenizer st = new StringTokenizer(br.readLine()); 
			N = Integer.parseInt(st.nextToken()); // 정수 개수
			answer = Integer.parseInt(st.nextToken()); // 합
			arr = new int[N];
			st = new StringTokenizer(br.readLine()); 
	 		for (int i = 0; i < arr.length; i++) {
				arr[i] =  Integer.parseInt(st.nextToken());
			}
	 		//Arrays.sort(arr);
	 		dfs(0,0);	
	        if(answer==0) count--; // S가 0이면 공집합(아무 원소도 포함되지 않는 것)을 빼야함 (문제에서 부분수열은 양의 크기만 가능하다 했음)
	 		System.out.println(count);
		}

		private static void dfs(int idx, int sum) {
        // dfs로 돌며 누적시키다가 위치를 나타내는 v이 마지막 위치로 오면 원하는 값인지 아닌지 체크하여 count
			if(idx ==N) {
				// 합이 정답과 같을 때 
				if(sum == answer) {
				count++;
				}
				return;
			}
				// 현재 값을 포함 시킬 때 순열
				dfs(idx+1, sum+arr[idx]);
				// 현재 값을 포함 안 시킬 때 순열
				dfs(idx+1, sum);			
		}
	}

공부 자료 : 조합

https://bcp0109.tistory.com/15

조합 Combination (Java)

https://geehye.github.io/baekjoon-1182/#

Backtracking 백준 알고리즘 자바 1182 ‘부분수열의 합’ 문제풀이

https://sudeky.tistory.com/126

(Baekjoon) brute-force - (1) 부분수열의 합( + 부분집합 출력)