카테고리: 완전탐색

문제

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

풀이 방식

모든 경우의 수는 각 원소를 뽑는다/안뽑는다로 나뉘기 때문에 2^N 입니다. 따라서 완전탐색을 통해 합이 S가되는 모든 경우의 수를 탐색해보겠습니다. 트리구조를 이루기 때문에 DFS 방식으로 풀 수 있습니다.

주의할 점은 모든 원소를 뽑지 않는 경우의 수도 포함이기 때문에 문제에서의 크기가 양수인 부분수열에 위배됩니다. 따라서 S가 0으로 주어진다면 공집할일 때의 경우의 수를 제외시켜야 하므로 결과값에서 -1 해주어야합니다.

1. dfs의 재귀 함수를 정의한다.

static void dfs(int index, int sum){
	//종료조건
    if(index == n) {
    	if(sum == s){
        	count++;
        }
        return;
    }

	//지금 인덱스 뽑는다
    dfs(index+1, sum + arr[index]);
    //지금 인덱스 안뽑는다.
    dfs(index+1, sum);

}

최종 코드

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

public class Main {
    static int n, s, count;
    static int[] arr;


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

        StringTokenizer st = new StringTokenizer(br.readLine());

        n = Integer.parseInt(st.nextToken());
        s = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        arr = new int[n];
        for(int i=0; i<n; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        //연속된 부부수열이 아니다 -> 투포인터 x
        //뽑느다/안뽑는다의 트리 형식 완전탐색 : dfs

        count = 0;
        dfs(0,0);
        //dfs의 경우의 수안에는 모든 원소를 뽑지 않는 경우도 포함이다(공집합)
        //공집합은 크기가 양수인 부분수열이 아니다.
        //공집합의 경우에도 결과가 0이 되기때문에 s가 0인 문제에서는 공집합의 경우의 수는 제외시켜준다.
        if (s == 0) {
            System.out.println(count - 1);
            return;
        }
        System.out.println(count);
    }

    static void dfs(int index, int sum){
        //종료조건
        if(index == n) {
            if(sum == s){
                count++;
            }
            return;
        }


        //지금 인덱스 뽑는다
        dfs(index+1, sum + arr[index]);
        //지금 인덱스 안뽑는다.
        dfs(index+1, sum);

    }
}