[JAVA] 백준 1182

 

 

 

1182번: 부분수열의 합

 

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

풀이

처음에는 부분 수열이 반드시 연속된 수열이여야 하는 줄 잘못 알고 누적합을 사용해서 모든 경우를 탐색하는 방식으로 문제를 해결하려고 했으나 답이 구해지지 않았다.

그래서 질문 게시판을 살펴보니 부분 수열은 연속될 필요가 없고 만약 연속된 부분 수열일 경우 연속이라는 단어가 붙어 있을 것이라는 답변이 있어 연속되지 않은 부분수열까지 모두 탐색하는 방식으로 만들었다.

📌 백트래킹 탐색

    public static void DFS(int depth, int num, int now){
        if(depth > N-1) return;
        if(num == S && depth > 0) answer++;

        for(int i=now; i<N; i++){
            if(!V[i]) {
                V[i] = true;
                DFS(depth + 1, num + D[i], i);
                V[i] = false;
            }
        }
    }

모든 수열들을 탐색하면서 방문하지 않은 노드들을 탐색하도록 백트래킹 탐색을 진행했다.

• 만약 부분 수열을 더한 값이 S라면 카운트하고 전체 수열의 크기가 넘어가면 다시 재귀를 돌아가서 탐색을 진행하도록 하였다.
• i를 now로 둔 이유는 이전 값들은 이전에 이미 탐색했기 때문에 다시 방문할 필요가 없다고 생각했다.

📌 전체 코드

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

class Main {
    static boolean[] V;
    static int N;
    static int S;
    static int answer= 0;
    static int[] D;
    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())+1;
        S = Integer.parseInt(st.nextToken());
        V = new boolean[N];

        st = new StringTokenizer(br.readLine(), " ");
        D = new int[N];
        for(int i=1; i<N; i++){
            D[i] = Integer.parseInt(st.nextToken());
        }
        DFS(0, 0, 1);
        System.out.println(answer);

    }
    public static void DFS(int depth, int num, int now){
        if(depth > N-1) return;
        if(num == S && depth > 0) answer++;

        for(int i=now; i<N; i++){
            if(!V[i]) {
                V[i] = true;
                DFS(depth + 1, num + D[i], i);
                V[i] = false;
            }
        }
    }

}

결과