[Algorithm/Java] SWEA 4837번 - 부분 집합의 합

---

부분집합의 합 (SWEA)

---

🔍 문제 풀이

문제 도식화

“1부터 12까지의 원소 중에서 정확히 N개를 뽑아서, 그 합이 K가 되는 경우의 수” 를 세는 문제

💻 코드

전체 코드

import java.io.*;
import java.util.*;

public class Solution {
    static int n, k, ans;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        // 배열 초기화
        arr = new int[12];
        for (int i = 0; i < 12; i++) {
            arr[i] = i + 1;
        }

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 뽑을 개수
            k = Integer.parseInt(st.nextToken()); // 목표 합
            ans = 0;

            dfs(0, 0, 0);
            System.out.println("#" + tc + " " + ans);
        }
    }

    static void dfs(int depth, int sum, int cnt) {
        // 1. 가지치기 (가장 마지막에 고민, 가장 위에 처리)
        if(sum > k) return; // 합이 이미 k 초과면 탐색 종료

        // 2. 종료조건 (depth와 관련)
        if(depth == 12){
            if(sum == k && cnt == n) ans ++;
            return;
        }

        // 3. dfs 탐색
        // (1) depth 번째 인덱스 사용
        dfs(depth + 1, sum + arr[depth] , cnt + 1);
        // (2) depth 번째 인덱스 미사용
        dfs(depth + 1, sum, cnt);

    }
}

스켈레톤 코드

import java.io.*;
import java.util.*;

public class Solution {
    static int n, k, ans;
    static int[] arr;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());

        // 1. 배열 초기화
        arr = new int[12];
        for (int i = 0; i < 12; i++) {
            arr[i] = i + 1;
        }

        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken()); // 뽑을 개수
            k = Integer.parseInt(st.nextToken()); // 목표 합
            ans = 0;

            dfs();
            System.out.println("#" + tc + " " + ans);
        }
    }

    static void dfs() {

    }
}