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

🔺 문제

1182번: 부분수열의 합

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, goal, 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 = Integer.parseInt(st.nextToken());
        goal = Integer.parseInt(st.nextToken());
        
        // 입력받기
        A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        // 백트래킹
        dfs(0, 0);
        System.out.println(ans);
    }
    
    private static void dfs(int cur, int tot) {
        if(cur == N)  return;        // 끝까지 돌았을 때
        else {
            if(A[cur] + tot == goal) {
                ans++;
            }
            // 부분수열, 현재 위치의 원소를 선택하거나 / 선택하지 않거나
           dfs(cur + 1, tot);        // 다음 인덱스로 넘어가기
           dfs(cur + 1, tot + A[i]); // 다음 인덱스로 넘겨주고 & 현재 위치 원소 선택
        }
    }
}
 

✅ 해결 아이디어
✔ 백트래킹 : 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘
- 매 순간 수를 더할지 / 말지를 통해 부분 수열의 합 계산 가능!

함수 인자로 현재까지의 함 (tot)도 함께 가져가게

 

---

🔺 다른 풀이들

- 깔끔한 풀이ㅠㅠ

로그인

---

💬 느낀 점

후엥 백트래킹 다시 머릿속에 집어넣어야 함

N과 M시리즈 다시 풀어~~

 

 

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

 

 

(+ 2회독 8.23)

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, S, cnt;
    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 = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        
        A = new int[N];
        st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0 ; i < N ; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        
        backtracking(0, 0);   
 
        if(S == 0) cnt--;    // S가 0인 경우, 공집합 제거
        System.out.println(cnt);
    }
    
    private static void backtracking(int tmp, int tot) {
        if(tmp == N) {
            if(tot == S) {
                cnt++;
            }
            return;
        }
            
        backtracking(tmp + 1, tot);             // 현재 위치 원소 선택 X, 다음 인덱스로 넘어감
        backtracking(tmp + 1, tot + A[tmp]);    // 현재 위치 원소 선택 O, 다음 인덱스로 넘어감
    } 
}

 

인자를 들고 가는 이 형식을 기억하좌,,,,!!

---

(참고)

✔ 풀이

https://log-laboratory.tistory.com/119

https://we1cometomeanings.tistory.com/266

 

 

✔ 백트래킹

[실전 알고리즘] 0x0C강 - 백트래킹