[백준/JAVA] 14225번: 부분수열의 합

🔺 문제

14225번: 부분수열의 합

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N;
    
    static int[] arr;
    static boolean[] visited = new boolean[20 * 1000000 + 1];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        N = Integer.parseInt(br.readLine());
        arr = new int[N];
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        dfs(0, 0);
 
        for(int i = 1 ; i < visited.length ; i++) {
            if(!visited[i]) {
                System.out.println(i);
                break;
            }
        }
    }
    
    private static void dfs(int depth, int sum) {
        if(depth == N) {
            visited[sum] = true;
            return;
        }
        
        dfs(depth + 1, sum + arr[depth]);   // 🔔 수열 S에서의 원소를 합하는 경우
        dfs(depth + 1, sum);                // 🔔 수열 S에서의 원소를 합하지 않는 경우
    }
    
}

✅ 해결 아이디어
✔ 브루트포스 + DFS
- 부분집합 합 구하기
 └ DFS
 └ 수열 S에서의 원소를 합하는 / 합하지 않는 경우 나눠서 재귀호출

 

💥 유의사항

• 수열에서 원소를 합하는 경우와 합하지 않는 경우를 분리해 구함

• 부분합 sum을 인자로 들고 가면서 업데이트 해주자

 

 

---

🔺 다른 풀이들

- 부분 수열의 합을 조합을 활용해서 푸심

백준 14225 부분수열의 합 (Java,자바)

 

 

- dfs문 안이 조금 다름

[백준] code.plus(브루트포스 - 재귀,JAVA)14225번, 부분수열의 합

---

💬 느낀 점

부분집합 원소의 합을 조합을 일일이 구해서 풀 생각을 했었는데...

자꾸 에러가 나서 다른 분들 풀이를 보고 작성했다...

 

코드가 생각보다 간단해서 당황..'

담에는 나도 이렇게 풀자!

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[JAVA] 백준 -부분 수열의 합 14225

[백준] 14225 부분수열의 합 - JAVA