[백준-1182] 부분수열의 합

난이도 : S3

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

Tag : BFS

 

문제 탐색하기 

- 부분 수열의 합중에 S가 되는 경우의 수를 구하면 되는 문제였습니다.

시도 1 😓

시간복잡도

각각의 숫자를 선택하는것은 서로에게 영향을 미치지 않습니다. 즉, 숫자 하나의 입장으로 보았을 때 선택을 하냐, 선택을 하지 않냐의 경우만 존재합니다.

숫자의 개수는 최대 20개 이므로 모든 경우의 수는 2^20 = 1,048,576 입니다.

모든 경우의 수를 살펴보아도 충분한 시간이였습니다.

 

선택 알고리즘

각각의 독립bfs를 활용하여 숫자를 선택하는 경우, 선택하지 않는 경우를 구현하였습니다.

 

구현 방법

1. 값을 입력받는다.

20개의 숫자와 N, S 총 22개의 숫자를 입력받기 때문에 편리한 Scanner대신에, BufferedReader와 StringTokenizer 조합을 사용하여 입력 받았습니다. 

 

2. dfs ( 0, 0, 0) 을 호출한다.

 

3. bfs를 구현한다.

이때 경우의 수는 2가지가있습니다.

선택하기 ,선택안하기가 있는데 선택했을 경우에는 전체 합에 해당 숫자를 더함

3-1 선택한다

dfs(cur + 1, sum + arr[cur], pickedCount + 1)

기존 합에 해당 숫자를 더하였으며 뽑은 숫자의 개수를 1증가 시켰습니다. 그후 다음 숫자를 가르킬 수 있도록 cur(커서)를 1증가시켰습니다.

 

3-2 선택하지 않는다.

dfs(cur + 1, sum, pickedCount);

 

기존 합을 그대로 넘긴다는 차이점을 제외하고 3-1과 동일합니다.

 

 

전체코드

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

class Main {

    private static int n;
    private static int s;
    private static int[] arr;
    private static int count = 0;

    public static void dfs(int cur, int sum) {

        if (cur == n) {
            if (sum == s) {
                count++;
            }
            return;
        }

        dfs(cur + 1, sum + arr[cur], pickedCount + 1); // 해당 숫자를 선택함.
        dfs(cur + 1, sum, pickedCount); // 해당 숫자를 선택하지 않음
    }

    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());
        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());
        }

        dfs(0, 0, 0);

        System.out.println(count);
    }
}

 

문제🚨

해당 코드로 테스트 케이스를 통과하지 못하였습니다.

dfs 구현쪽에서 잘못된걸까 그쪽을 고민하였지만 잘못된 부분을 찾지 못하였습니다.

해답은 문제에 있었습니다.

 

 

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서

 

테스트케이스는 S가 0인 부분 수열합의 경우의 수를 계산하는 것이였는데, 크기가 0인 공집합이 경우의 수에 추가된다는 것이 문제였습니다. 

문제를 알았으니 해결하는 방법은 간단했습니다.

1. s==0일때 경우의 수를 하나 빼주기

2. 뽑은 개수를 트래킹 하기

저가 떠오른 방법은 2가지였으며 좀 더 직관적이라고 판단한 2번을 선택하였습니다.

시도 2

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

class Main {

    private static int n;
    private static int s;
    private static int[] arr;
    private static int count = 0;

    public static void dfs(int cur, int sum, int pickedCount) {

        if (cur == n) {
            if (sum == s && pickedCount > 0) {
                count++;
            }
            return;
        }

        dfs(cur + 1, sum + arr[cur], pickedCount + 1); // 해당 숫자를 선택함.
        dfs(cur + 1, sum, pickedCount); // 해당 숫자를 선택하지 않음
    }

    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());
        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());
        }

        dfs(0, 0, 0);

        System.out.println(count);
    }
}

 

이렇게 하니 테스트 케이스를 통과하였고 제출하여 정답 처리를 받았습니다.

 

마무리

친절하게 0인 테스트 케이스를 주었기 때문에 알아차릴 수 있었지 만약 주어지지 않았더라면 엣지 케이스를 발견하는데 시간이 더 소요되었을 것 같습니다. 스스로 엣지 케이스는 뭐가 있을지 생각해 보려고 노력을 해야겠다고 깨달았습니다.