[백준] 1182번 - 부분수열의 합

1182번 - 부분수열의 합

 

<문제>

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

1182번: 부분수열의 합

 

<문제 풀이>

DFS를 통해 모든 경우의 수를 탐색한 뒤 depth가 N이고, 부분 수열의 합이 S일 경우 count를 1씩 증가하여 출력 값을 구한다. 

이때 주의해야 할 점은 S가 0일 때, 부분 수열의 어떠한 수도 선택되지 않는 경우이다. S가 0이 아닐 경우 앞의 경우는 고려사항이 아니다. 즉, S가 0일 때만 count에서 1을 빼주면 된다. 

dfs(idx + 1, sum + arr[idx]); //왼쪽
dfs(idx + 1, sum); //오른쪽

 

<코드>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N, S;
	static int[] arr;
	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());
		arr = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dfs(0, 0);
		if(S == 0) { //S가 0일 경우 cnt에 1 빼줌
			cnt--;
		}
		System.out.println(cnt);
	}
	
	public static void dfs(int depth, int sum) {
		if(depth == N) { //깊이가 N과 같고
			if(sum == S) { //부분 수열의 합도 S와 같다면 
				cnt++; //cnt에 1 더함
			}
			return;
		}
		dfs(depth + 1, sum + arr[depth]); //왼쪽
		dfs(depth + 1, sum); //오른쪽
	}
}

 

<결과>

 

 

2023.04.07