[백준] 부분수열의 합 in Java

📍 문제

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

 

주어진 수열들의 합 중에 s가 되는 경우의 수를 찾으면 된다.

만약 s가 3이고 수열이 -1 4 1 2 라면

3이 되는 수열은 -1 4,1 2로 2개이다.

📍 코드 설명

해당 수를 보고 더할지 말지를 결정하면서 끝까지 내려간다.

트리 내부는 합

간단하게 일부만 트리를 그려보자면 아래와 같다.

1. -7을 선택하지 않고, -3을 선택하지 않고, -2를 선택하지 않고, 5를 선택하지 않고, 8을 선택하지 않으면 총 합은 0이다. (공집합)

2. 가능한 선택이 끝났으므로 한칸 위로 올라간다.

3. 한칸 위로 올라가서 8을 포함한다. 총 합은 8이다.

4. 8에서 가능한 선택이 끝났으므로 5로 올라간다.

5. 5를 선택한다.

6. 8을 선택하지 않으면 총 합은 5이다.

7. 8을 선택하면 총 합은 13이다.

 

이런식으로 전부 가능한 조합을 계산할 수 있다.

 

N의 크기가 크지 않고, 시간 제한도 2초이기때문에 이렇게 백트래킹으로 풀 수 있다.

시간 복잡도를 간단하게라도 계산해보자면

가능한 부분수열을 전부 탐색하는 것이므로 부분수열의 개수인 O(2^n)이고 n이 최대 20이므로 2의 20승은 1,048,576로 100만번이다.

1억을 1초라고 치면 굉장히 널널하다고 볼 수 있다.

📍 코드

포함할것, 안할 것을 둘 다 탐색해야하기때문에 둘다 재귀로 호출한다.

이때 끝까지 탐색을 한 뒤에 합이 s랑 같은지를 판단해야한다.

 

또한 주의할 점은 해당 문제 조건에서 크기가 양수인 부분수열 중에서 라는 조건이 있기 때문에 s가 0이라면 공집합인 경우를 빼주어야지 정답이다. 그래서 문제에서도 예시로 0인 경우를 준 것 같다.

 

✔️ 코드

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

public class Main {
  
  static int answer= 0;
  static int s;
  static int n;
  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());
      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());
      }
      
      function(0, 0);
      
      // 공집합까지 포함해서 s가 0인 경우 공집합을 제외해주어야한다.
      if(s == 0) answer--;
      System.out.println(answer);
	}

	static void function(int k, int sum) {
	  if(k == n) {
	    if(sum == s) answer++;
	    return;
	  }
	  
	 function(k + 1, sum);
	 function(k + 1, sum + arr[k]);
	}
}

 

📍 틀린이유

백트래킹 문제인건 파악을 했으나,

기준을 어떻게 잡아야할지 헷갈렸다.

 

원소를 기준으로 트리를 그리니까 기억해야할 상태가 너무 많아서 제대로 풀지 못했다.

합을 기준으로 그리고 선택한다 안한다로 쭉 가지치기를 했으면 됐는데, 아직 백트래킹은 익숙치 않은 것 같다.

 

더 다양한 문제를 풀어봐야할듯

 

📍 기억할 것

백트래킹은 트리 그림을 그릴 때 어떻게 그릴지가 정말 중요한 것 같다.

다양한 문제를 풀면서 기준을 파악해야할 것 같다.