[백준] 1182번: 부분수열의 합 (Java)

💡문제 분석 요약

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열에서 그 수열의 원소를 모두 더한 값이 S가 되는 경우의 수를 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 256MB

 

💡알고리즘 설계

• `numbers` 배열에 N개의 정수를 입력받는다.
• 부분 수열의 길이(`depth`)는 1~N까지 가능하다. 각 길이에 대해 백트래킹을 수행한다.
• 백트래킹 메서드
  • 현재 깊이가 목표 깊이와 같으면, (`curDepth == depth`)
    • 부분수열의 합(`sum`)이 S인지 확인하고 `result`를 갱신한다.
  • 그렇지 않으면, 현재 위치(`start`)부터 N까지의 숫자에 대해
    • 해당 숫자를 `sum`에 더한다.
    • 다음 위치로 이동하여 메서드를 재귀 호출한다.
    • 백트래킹 후 `sum` 에서 해당 숫자를 뺀다. (원상 복구)
  • ex) {-7}, {-3}, {-2}, {5}, {8}, {-7, -3}, {-7, -2}, {-7, 5}, {-7, 8}, {-3, -2}, {-3, 5}, {-3, 8} … 의 순서로 진행.

 

💡코드

import java.io.*;

public class Main {
    static int n, s;
    static int[] numbers;
    static boolean[] visited;
    static int depth, sum, result = 0;

    static void backTrack(int start, int curDepth) {
        if(curDepth == depth) {
            if(sum == s) result++;
            return;
        }

        for(int i=start; i<n; i++) {
            if(visited[i]) continue;
            sum += numbers[i]; visited[i] = true;
            backTrack(i+1, curDepth+1);
            sum -= numbers[i]; visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        s = Integer.parseInt(input[1]);
        numbers = new int[n];
        String[] numInput = br.readLine().split( " ");
        for(int i=0; i<numInput.length; i++) {
            numbers[i] = Integer.parseInt(numInput[i]);
        }

        for(int i=1; i<=n; i++) {
            sum = 0; depth = i;
            visited = new boolean[n];
            backTrack(0, 0);
        }
        System.out.println(result);
    }
}

 

💡시간복잡도

$O(2^N)$

 

💡 느낀점 or 기억할정보

이 문제는 다른 풀이를 참고하지 않고 한 번에 성공했다!

`Integer.parseInt()` 메서드는 음수를 포함한 문자열도 정수로 변환할 수 있다.
(”-7” 문자열을 `Integer.parseInt()`로 변환하면 -7이라는 정수값을 얻을 수 있다.)