[SWEA 2817번] 부분 수열의 합

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AV7IzvG6EksDFAXB&categoryId=AV7IzvG6EksDFAXB&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=1

SW Expert Academy

 

DFS

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

public class Solution {

    static int N;

    static int K;

    static int[] num;

    static int result;

    static int sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test < T + 1; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            result = 0;
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            num = new int[N];
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }
            sum = 0;
            solution(0);
            System.out.println("#" + test + " " + result);
        }
    }

    static void solution(int level) {
        if (sum == K) {
            result++;
            return;
        }

        if (level == N) {
            return;
        }


        for (int i = level; i < N; i++) {
            sum += num[i];
            if (sum > K) {
                sum -= num[i];
                continue;
            }
            solution(i + 1);
            sum -= num[i];
        }
    }
}

 

DP

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

public class Solution {

    static int N;

    static int K;

    static int[] num;

    static int result;

    static int sum;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(br.readLine());
        for (int test = 1; test < T + 1; test++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            result = 0;
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            st = new StringTokenizer(br.readLine());
            num = new int[N];
            for (int i = 0; i < N; i++) {
                num[i] = Integer.parseInt(st.nextToken());
            }
            solution();
            System.out.println("#" + test + " " + result);
        }
    }

    static void solution() {
        int[] dp = new int[K + 1];
        dp[0] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = K; j >= num[i]; j--) {
                dp[j] += dp[j - num[i]];
            }
        }

        result = dp[K];
    }
}

 

dfs로 풀면 간단한 문제였다. 하지만 시간초과 공부를 해야되서 DP로 다시 풀어봤다.

DP의 핵심은 가짓수로 파악해서 풀면된다.