[BOJ_1182]부분수열의 합 (실버 2) - JAVA

---

🐾 알고리즘

• 조합 혹은 부분집합
• 백트래킹

---

🐾 생각 포인트

• 부분수열이라고 무조건 연속된 수열이 아니다.
• 수열 내에서 1개, 2개, .. N개를 선택하는 조합론을 활용하자.
• 조합이 완성될 때마다 합을 비교해서 계수해주자.

 

---

🐾 소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int S;
	static int[] arr;
	static boolean[] visited;
	static int cnt;
	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()); // N개의 정수로 이루어진 수열
		S = Integer.parseInt(st.nextToken()); // 부분수열의 합이 s

		arr = new int[N];
		visited = new boolean[N];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		} // 입력완

		// 합이 s가 되는 부분수열의 개수 구하기!
		// i개 뽑음!
		for (int i = 1; i <= N; i++) {
			combination(arr, visited, 0, i);
		}
		
		System.out.println(cnt);

	}

	private static void combination(int[] arr, boolean[] visited, int start, int r) {
		if (r == 0) {
			sum(arr, visited);
			return;
		} else {
			for (int i = start; i < arr.length; i++) {
				visited[i] = true;
				combination(arr, visited, i + 1, r - 1);
				visited[i] = false;
			}
		}
	}

	// 부분수열의 합 구하기
	private static void sum(int[] arr, boolean[] visited) {
		int sum = 0;
		for (int i = 0; i < arr.length; i++) {
			if (visited[i]) {
				sum = sum + arr[i];
			}
		}
		if(sum == S) {
			cnt++;
		}
	}

}

---

😵‍💫 공부해야 할 점

• 조합론에 대해 깊이있게 공부해야할 것 같다. 조합론 알고리즘 자체를 외워버리다 보니, 이해해서 풀기보다는 암기해서 푸는 느낌이 강하다. 그래서 휘발성이 강하다 ㅠ.ㅠ😂😂