백준 JAVA 1182번 부분수열의 합 리뷰

 블로그 이전, 2023. 5. 11. 23:14 에 작성했던 글입니다.

1.풀이

dfs, 재귀함수로 부분집합을 구하면 된다. 

지금 위치를 선택하거나, 선택하지 않거나 를 재귀함수로 계속 호출하면 된다.

합(s)이 0이면 공집합도 하나 포함돼서 -1 해줘야 한다. 

 

초보인 나에게 도움 되었던 영상들, 이걸 보고서야 뭔지 감이 왔다. 

추천합니다.

1.[자료구조 알고리즘] Graph 검색 DFS, BFS 구현 in Java
https://youtu.be/_hxFgg7TLZQ
2.재귀함수란? 재귀 호출 | 아직도 어렵다면 무조건 클릭!!!!
https://youtu.be/yio6FyP1N2k
3.[PYTHON 재귀 10] 반복문 및 재귀 함수를 사용하여 부분집합 만들기
https://youtu.be/MkAud41ijhE
4.[PYTHON 재귀 12] 부분합 문제 - 재귀함수를 사용한 부분집합으로 해결
https://youtu.be/FmpjkKeEYX0

2.나의 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main{
    static int[] arr;
    static int n,s, count=0;
    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<arr.length; i++){
            arr[i]=Integer.parseInt(st.nextToken());

        }
        dfs(0,0);

        if(s==0){ //합이 0이면 공집합도 포함하니까 count-1 해야함
            System.out.println(count-1); 
        }else{
            System.out.println(count);
        }
    }
    public static void dfs(int dep, int sum){
        //종료조건
        if(dep==n) { //dfs로 돌며 누적시키다가 위치를 나타내는 dep가 n까지 오고 sum==s일때 종료
            if(sum == s) {
                count++;
            }
            return;
        }
            //재귀함수
            dfs(dep+1, sum+arr[dep]); //지금 위치의 원소를 사용하면 sum+현재 원소를 더함
            dfs(dep+1, sum); //안 사용하면 안 더함
        }
    }