[SWEA] - 2817. 부분 수열의 합 (D3)

[문제]

A1, A2, ... , AN의 N개의 자연수가 주어졌을 때, 최소 1개 이상의 수를 선택하여 그 합이 K가 되는 경우의 수를 구하는 프로그램을 작성하시오.

[입력]
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스의 첫 번째 줄에는 2개의 자연수 N(1 ≤ N ≤ 20)과 K(1 ≤ K ≤ 1000)가 주어진다.
두 번째 줄에는 N개의 자연수 수열 A가 주어진다. 수열의 원소인 N개의 자연수는 공백을 사이에 두고 주어지며, 1 이상 100 이하임이 보장된다.

[출력]
각 테스트 케이스마다 ‘#x ’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고, 부분 수열의 합이 K가 되는 경우의 수를 출력한다.

문제 풀기

2817. 부분 수열의 합

 

---

[풀이]

• dfs 알고리즘을 통해 풀이
• 수열에 있는 숫자를 포함하는 경우와 그렇지 않은 경우로 나누어 탐색
• 합이 K 가 되었거나, index가 N이 되었을 때 return을 해줌

import java.util.Scanner;

class Solution {
	public static int arr[];
	public static int n, k;
	public static int cnt;
	
	public static void main(String[] args) throws Exception {		
		Scanner sc = new Scanner(System.in);
		
		int t = sc.nextInt();
		
		for(int tc=1; tc<=t; tc++) {
			n = sc.nextInt();
			k = sc.nextInt();

			arr = new int[n];
			
			for(int i=0; i<n; i++) arr[i] = sc.nextInt();
			
			cnt = 0;
			solve(0, 0);
			
			System.out.format("#%d %d\n", tc, cnt);
		}
	}
	
	public static void solve(int sum, int idx) {
		if(sum == k) {
			cnt++;
			return;
		}
		else if(sum > k || idx >= n) return;
		
		solve(sum+arr[idx], idx+1);
		solve(sum, idx+1);
	}
}