[BOJ] 1182 부분수열의 합 Java 풀이

 

 

BOJ 1182 부분수열의 합

 

문제를 잘 이해해야겠다. 지문에서 크기가 양수인 부분수열 중에서~ 부분이 있는데 크기가 양수라는 말 그대로 이해하지 못하고, 값을 양수라고 생각했다. 지금 보면 헷갈릴 이유가 없는데, 처음 접했을 때는 이상하게 헷갈렸다.

크기가 양수인 부분수열이라 하면 아무 것도 선택하지 않는 상황만을 제외하면 되겠다. 그런 경우도 부분수열이라고 할 수 있는지는 몰랐지만 아마 집합에서의 부분집합에서 공집합 개념과 유사하지 않은가 싶다.

풀이는 먼저 DFS, 백트래킹 개념을 이용하면 된다. 수열의 각 원소로 구할 수 있는 값을 모두 구하면서, 값이 S와 동일한지 아닌지를 체크하면 되겠다. 시간 제한이 2초로 주어졌는데, 수열의 길이인 N의 최댓값이 20이다. 각 원소를 합에 포함할 지, 하지 않을지 두 가지 선택지를 모든 원소에서 탐색한다고 하면 2^20 == 1048576 이다. 모든 경우의 수를 탐색해도 시간 제한 2초에 충분하게 풀어낼 수 있다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	static int N, S;
	static int arr[], result[];
	static int cnt;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		S = Integer.parseInt(st.nextToken());
		
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dfs(0, 0);
		if(S == 0) {
			System.out.println(cnt-1);
		}else {
			System.out.println(cnt);
		}
	}
	
	private static void dfs(int index, int sum) {
		if(index == N) {
			if(sum == S) {
				cnt++;
			}
			return;
		}
		dfs(index+1, sum+arr[index]);
		dfs(index+1, sum);
	}
}

 

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

현재 원소를 합에 포함하는 경우와, 하지 않는 경우를 모두 탐색한다는 것만 설계 과정에서 떠올려냈다면, dfs에서 다음 호출을 하는 부분은 어렵지 않게 구현할 수 있다. 만약 알면서도 이 구현이 익숙하지 않다면 다양한 백트래킹 문제를 연습해볼 필요가 있겠다.(나 포함)

cnt를 모두 해내면 main 함수에서 출력만 하면 되는데, 유의할 점은 S가 0인 상황이다. sum이 0이 되는 경우는 음수와 양수의 합으로 만들어지거나, 모든 수를 선택하지 않은 경우가 되겠다. 모든 원소를 합에 포함하지 않는 경우는 크기가 양수인 부분수열이라는 조건에 부합하지 않아서, 그런 경우에서만 cnt-1을 출력해주면 된다.