자바(백준) 1182 부분 수열의 합

풀이 방법

이 문제는 배열을 집합이라 생각하고, 부분 집합들의 원소들의 합이 주어진 합을 만족시키면 count를 ++해주는 방식으로 생각했다. backTracking 함수를 호출할 때, 인자에 sum을 1222222를 넣었다. 왜냐하면 만약 주어진 합이 0일 때, 처음에 인자를 0으로 보낸다면 count를 늘리고 시작해서 답이 틀리게 된다. 그래서 주어진 조건을 보면 sum은 절댓값 1,000,000보다 작거나 같다고 주어져있어서, 이 조건을 뛰어넘는 숫자를 대입하여 그러한 실수를 방지했다. 

 

사용 개념

재귀 함수

 

코드

package BackTracking;
 
import java.io.*;
import java.util.*;
 
public class BOJ1182 {
    static int[] arr;
    static int resultsum;
    static boolean[] visit;
    static int index;
    static int count = 0;
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        index = Integer.parseInt(st.nextToken());
        resultsum = Integer.parseInt(st.nextToken());
 
        arr = new int[index];
        visit = new boolean[index];
 
        st = new StringTokenizer(br.readLine());
 
        for(int i = 0; i < index; i++)
            arr[i] = Integer.parseInt(st.nextToken());
        
        backTracking(0,1222222);
 
        System.out.print(count);
    }
    static void backTracking(int start, int sum){
        if(sum == resultsum) {
            count++;
        }
        if(start >= index) return;
 
        for(int i = start; i < index; i++){
            if(visit[i]) continue;
 
            visit[i] = true;
            sum = getsum();
            backTracking(i+1, sum);
            visit[i] = false;
        }
    }
    static int getsum(){
        int sum = 0;
        for(int i = 0; i < index; i++){
            if(visit[i]) sum += arr[i];
        }
        return sum;
    }
}
 

---

오답 노트 & 새로 알게 된 점(2021.10.13)

다시 풀어봤는데 다른 풀이를 생각해서 올려본다.

 

여기서는 부분수열의 합이 S를 만족하느냐이다.

그렇다면 집합에서 부분집합을 구하면 된다.

즉, 아래의 사진처럼 구한다.

 

cnt가 1 일때 -7을 포함하는 경우만 쓴 것이다. 포함하지 않는 경우도 생각해서 총 32가지 = 2^5가 나온다.

 

여기서 제일 중요한 점은 S가 0으로 주어질 경우 경우의 수를 한가지 빼줘야한다.

 

왜냐하면 S가 0으로 주어지고, 수열이 하나도 포함되지 않을 경우도 

경우의 수에 들어가기 때문에 한 개를 빼줘야한다.

---

코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int atoi(String str) {
        return Integer.parseInt(str);
    }
    static int N, S,ans;
    static int A[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        N = atoi(st.nextToken());
        S = atoi(st.nextToken());
 
        A = new int[N + 1];
 
        st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= N; i++) {
            A[i] = atoi(st.nextToken());
        }
 
        pro(1,0);
 
        if(S == 0) ans--;
 
        System.out.println(ans);
    }
 
    static void pro(int cnt, int sum) {
        if (cnt == N + 1) {
            if(sum == S) ans++;
            return;
        }
 
        pro(cnt + 1, sum + A[cnt]);
        pro(cnt + 1, sum);
    }
}