문제 url:
부분수열의 합
문제:
🤔 문제 알아보기
정수의 개수 N개 더한 값의 기준인 S를 입력받는다.
그리고, 합이 S가 되는 부분수열의 개수를 출력받는다고 한다.
여기서 부분수열(subsequence)이란?
주어진 수열의 일부 항을 원래 순서대로 나열하여 얻을 수 있는 수열
즉, TC 값인 -7, -3, -2, 5, 8에서 얻을 수 있는 부분수열은{ } (빈 집합)
{-7}, {-3}, {-2}, {5}, {8}
{-7, -3}, {-7, -2}, {-7, 5}, {-7, 8}, {-3, -2}, {-3, 5}, {-3, 8}, {-2, 5}, {-2, 8}, {5, 8}
{-7, -3, -2}, {-7, -3, 5}, {-7, -3, 8}, {-7, -2, 5}, {-7, -2, 8}, {-7, 5, 8}, {-3, -2, 5}, {-3, -2, 8}, {-3, 5, 8}, {-2, 5, 8}
{-7, -3, -2, 5}, {-7, -3, -2, 8}, {-7, -3, 5, 8}, {-7, -2, 5, 8}, {-3, -2, 5, 8}
{-7, -3, -2, 5, 8}
이렇게 존재한다고 한다. 그래고 여담으로 N개의 배열에서 나올 수 있는 부분수열의 수는 (1은 빈 집합을 제외하기 위해 뺴기)로 구할 수 있다.
자! 문제의 조건을 알아봤고, 푸는 방법을 설명드리자면
부분수열을 찾는 방법은 숫자를 선택하거나 선택하지 않는 경우가 존재한다.
그렇다면 만약 첫 번째 값을 입력받았을 때, 다음 수를 선택하거나 혹은 선택하지 않는 경우 모두 고려한다면 부분수열을 찾을 수 있을 것이다.
우리는 이를 위해 두 경우에 대한 재귀호출을 통해 구해보고자 한다.
🐱👤 실제 코드
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int[] arr;
static int N;
static int S;
static int cnt = 0;
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());
st = new StringTokenizer(br.readLine());
arr = new int[N];
for(int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
dfs(0, 0);
if(S == 0) {
cnt--;
}
System.out.println(cnt);
}
static void dfs(int depth, int sum) {
if(depth == N) {
if(sum == S) {
cnt++;
}
return;
}
dfs(depth +1, sum + arr[depth]);
dfs(depth +1, sum );
}
}
😎 코드 풀이 및 해석
위에서 부분수열을 구하는 방법에 대해서 설명하였다. 해당 방법을 잘 떠올리면 코드가 어렵지 않을 것 같다.
하지만! 그래도 코드가 길지 않으니 하나씩 설명해보자면,
1번 째 코드
static void dfs(int depth, int sum) {
if(depth == N) {
if(sum == S) {
cnt++;
}
return;
}
dfs(depth +1, sum + arr[depth]);
dfs(depth +1, sum );
}dfs메서드는 depth와 sum을 파라미터 값으로 받는다.
여기서 depth는 우리 for문시 받는 i값처럼 이해하면 될 것이다.
그래서 현재 depth가 N과 같다면 즉, N까지 반복을 완료했을 때 sum이 S와 같다면 cnt를 더한다.
5 0
-7 -3 -2 5 8
TC로 위와 같은 값을 가졌을 때, 우리는 {안고름,-3, -2, 5, 안고름 } 에서 S가 0이 되는 것을 찾을 수 있다. 이때 cnt변수를 1씩 더하라는 얘기이다.
dfs(depth +1, sum + arr[depth]);
dfs(depth +1, sum );그럼 다음 아래의 두 재귀호출을 진행하는데, 우리는 위에서 부분수열을 구하는 방법으로
숫자를 고르는 경우와 고르지 않는 경우가 존재하고 이 둘을 모두 고려한다고 했다.
즉, 첫번째 dfs는 숫자를 선택한 재귀호출로 sum에 인덱스 depth에 대한 값이 누적합이 될 것이고,
두 번째 dfs는 숫자를 선택하지 않는 재귀호출로 현재 sum과 depth +1만 해주어 반복을 이어 나간다.
두 번째 코드
if(S == 0) {
cnt--;
}
System.out.println(cnt);마지막 출력 부분인데, 우리 아까 위에서 부분수열의 개수()에서 -1을 빼준 이유를 기억하는가?
그 이유가 빈 집합을 빼주기 위해서 였다.
근데, 만약 구해야 하는 값 S가 0인 경우라면? 빈 배열은 sum이 자동적으로 0이기 때문에 현재 TC처럼 구하면 출력이 1이 아니라 2가 될 것이다.
그래서 S가 0일 경우 빈 집합이 포함되는 것을 예외처리 해주는 것이다.
