[BOJ] 1182. 부분수열의 합

2021. 4. 21. 16:55알고리즘/백준 문제 풀이

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

접근 방법

처음에 코드를 순차적으로 합이 되는 경우만 생각을 해보았다.

하지만

예제에 { 2 0 } { 0 , 0 } 이라면 답은 3이 된다는 사실을 알게 되어

백트래킹을 사용해서 코드를 다시 짜게 되었다.

주의 사항

Need Know

  1. BackTracking

전체 코드 ( Java )

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

class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N;
    static int S;
    static int[] arr;
    static int count = 0;
    public static void main(String[] args) throws IOException {
        set();
        solve();

        br.close();
        bw.flush();
        bw.close();
    }

    static void set() throws IOException {
        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());
        }
    }

    static void solve() throws IOException {
        for(int i=0; i<N; i++){
            backtracking(arr[i], i);
        }

        bw.write(count+"");
    }
    static void backtracking(int total, int depth){
        if (depth == N - 1 && total == S) {
            count++;
        }
        depth++;
        if (depth < N) {
            backtracking(total + arr[depth], depth);
            backtracking(total, depth);
        }
    }
}

'알고리즘 > 백준 문제 풀이' 카테고리의 다른 글

[BOJ] 10800. 컬러볼  (0) 2021.09.18
[BOJ] 20056. 마법사 상어와 파이어볼  (0) 2021.09.18
[BOJ] 2573. 빙산  (0) 2021.03.26
[BOJ] 2178. 미로 탐색  (0) 2021.03.16
[BOJ] 2606. 바이러스  (0) 2021.03.16