내가 생각했을때 문제에서 원하는부분
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000)
둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다.
주어지는 정수의 절댓값은 100,000을 넘지 않는다.
첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
내가 이 문제를 보고 생각해본 부분
BufferedReader와 StringTokenizer를 사용해서 입력을 받았다.
재귀함수 findSubsequenceSum은 현재 인덱스와 현재 합을 매개변수로 받아,
모든 부분 수열의 합을 계산해준다.
현재 원소를 포함하는 경우와 포함하지 않는 경우로 나누어 재귀 호출을 해준다.
부분 수열의 합이 S와 같을 때마다 count를 증가시킨다.
모든 부분 수열을 탐색한 후,
최종적으로 count를 출력한다.
코드로 구현
package baekjoon.baekjoon_24;
import java.io.*;
import java.util.StringTokenizer;
// 백준 1182번 문제
public class Main846 {
static int N;
static int S;
static int[] numbers;
static int count = 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());
numbers = new int[N];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
// 부분 수열의 합을 찾기 위한 재귀 호출
findSubsequenceSum(0, 0);
System.out.println(count);
br.close();
}
static void findSubsequenceSum(int index, int currentSum) {
if(index == N) {
return;
}
// 현재 원소를 포함하는 경우
currentSum += numbers[index];
if(currentSum == S) {
count++;
}
findSubsequenceSum(index + 1, currentSum);
// 현재 원소를 포함하지 않는 경우
currentSum -= numbers[index];
findSubsequenceSum(index + 1, currentSum);
}
}
코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.