📌 문제 탐색하기
- 입력:
- 첫째 줄 : 정수의 개수를 나타내는 N과 정수 S
- 둘째 줄 : N개의 크기를 갖는 수열의 원소들(빈칸을 두고)
- 출력:
- N개로 이루어진 수열들 중에 원소를 다 더한 값이 S를 만족하는 부분수열의 개수
📌 어떤 알고리즘?
- 백트래킹(BackTracking)
- 백트래킹은 모든 가능한 경우의 수를 탐색하면서, 조건에 맞지 않는 경우를 가지치기(pruning)하며 연산을 줄이는 방법이다. 이 문제에서는 불필요한 가지치기 없이 모든 부분수열을 탐색하기 때문에, 가지치기는 이루어지지 않지만, 백트래킹의 형태로 문제를 해결할 수 있다.
- 재귀(Recursion)
- 재귀 호출을 통해 배열의 각 원소에 대해 포함 혹은 포함하지 않는 2가지의 경우로 나눈다.
- index가 N에 도달하면 종료를 하고, 이때까지 더한 값이 S와 같으면 count를 증가시킨다.
📌 코드 설계하기
- 입력: N, S 값을 입력받고 배열 arr에 N개의 정수를 저장한다.
- 부분집합 탐색:
- 재귀 함수 answer를 통해 현재 인덱스의 원소를 선택하거나 선택하지 않고 다음 단계로 진행한다.
- 재귀 탐색을 통해 모든 부분집합을 탐색한다.
- 조건 체크:
- 인덱스가 끝까지 도달했을 때 (index == N), 현재 부분수열의 합 sum이 S와 일치하는지 확인하고, 일치한다면 count를 증가시킨다.
- 출력:
- S가 0일 때, 아무것도 선택하지 않은 빈 부분집합이 하나 추가되어 count가 +1 되는 경우를 방지하기 위해 S == 0일 경우 count에서 1을 빼준다.
📌 시도 회차 수정 사항
- 초기 구현:
- 재귀 함수로 모든 부분집합을 탐색하며 sum이 S와 일치하는지 확인하였다.
- 수정:
- S == 0일 때 빈 부분집합을 빼주기 위해 count-- 구문을 추가하여 정확한 결과를 출력하도록 수정하였다.
📌 정답 코드
package BOJ_1182;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BOJ_1182 {
static StringTokenizer st;
static int N, S;
static int[] arr;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
st = new StringTokenizer(bf.readLine(), " ");
N = Integer.parseInt(st.nextToken());
S = Integer.parseInt(st.nextToken());
arr = new int[N];
int i = 0;
st = new StringTokenizer(bf.readLine(), " ");
while (st.hasMoreElements()) {
arr[i++] = Integer.parseInt(st.nextToken());
}
answer(0, 0);
if (S == 0) count--;
System.out.println(count);
}
public static void answer(int index, int sum) {
if (index == N) {
if (sum == S) {
count++;
}
return;
}
answer(index + 1, sum + arr[index]);
answer(index + 1, sum);
}
}
📌 시간 복잡도?
- 시간 복잡도
- 각 원소를 선택하거나 선택하지 않는 방식으로 2^N개의 부분집합을 탐색하게 된다.
- 최악의 경우, N=20일 때, 2^20 = 1048576 가지 경우를 계산하게 되고, 제한 시간안에 충분히 해결이 가능하다.
- 시간복잡도는 O(2^N)
- 공간 복잡도
- 재귀 호출이 최대 N 단계 까지 진행될 수 있고, arr 배열이 N개의 요소를 담고 있다.
- 공간복잡도는 O(N)
