[백준] 1182번 부분수열의 합 JAVA (자바) 풀이

문제 1182번 

 :  N개의 정수로 이루어진 수열

    크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하기

 

 

[입력]

 :  첫 줄에 정수 개수 N, 정수 S (1 ≤ N ≤ 20, |S| ≤ 1,000,000)
    둘째 줄에 N개의 수열이 공백으로 구분

[출력]

 : 합이 S가 되는 부분수열 개수 출력

 

[과정]

 - [공통] 공집합일 경우를 생각해야 하므로 S = 0 이라면 -1 하고 시작한다

 

 - 재귀적 백트래킹

• 반복문을 쓰지 않아서 좀 더 직관적으로 코드를 간결하게 볼 수 있다
• dfs(next,sum);         
• dfs(next,sum+arr[start]);

 예) [3, 7, 2] / S=9

 

       backtrack(0, 0)       
       ├─ backtrack(1, 0) 

       │   ├─ backtrack(2, 0) 
       │   │   ├─ backtrack(3, 0) 
       │   │   └─ backtrack(3, 2) 

       │   │
       │   └─ backtrack(2, 7)
       │        ├─ backtrack(3, 7) 
       │        └─ backtrack(3, 9) 

       │   
       └─ backtrack(1, 3)    

            ├─ backtrack(2, 3) 
            │   ├─ backtrack(3, 3)
            │   └─ backtrack(3, 5)

            │
            └─ backtrack(2, 10) 
                 ├─ backtrack(3, 10) 
                 └─ backtrack(3, 12)

 

 

- 브루트 포스 

• 재귀가 아닌 반복문을 사용할 경우 이해가 더 쉽다

1. for문을 통해 dfs 시작지점 이동해가며 실행

2. sum 값을 초기부터 입력해줌으로서 공집합 코드는 제외해도 무방하다

3. for문을 통해 dfs 다음지점도 순차적으로 이동

 

 

 [백트래킹 코드]

import java.util.*;
import java.io.*;
public class Main{
    static int N, S, arr[];
    static int count=0;
    
    public static void main(String args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        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 =1; i<=N; i++){
            arr[i]=Integer.parseInt(st.nextToken());
        }
        
        back(0,0);
        
        if(S == 0){
            System.out.println(count-1);
        }
        else{
        System.out.println(count);
        }
    }
    
    public static void back(int start, int result){
        if(start == N){
            if(result == S)
                count++;
            return;
        }
        
        back(start+1, result+arr[start]);
        back(start+1, result);
    }
}

 

 

 [해설]
     

 :  static int N, S, arr[];  수열 개수, 부분 수열 합, 수열 배열
    static int count=0;  출력할 부분수열 개수

 

 :  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<N; i++){  수열 넣기
            arr[i]=Integer.parseInt(st.nextToken());
    }
        
 :  back(0,0);  백트래킹 시작
        
 :  if(S == 0){  0일때만 공집합 포함 X
            System.out.println(count-1);
    }
    else{ count 출력
            System.out.println(count);
    }
    
 :  public static void back(int start, int result){  start는 index 값, result는 수열 합이라고 생각하면 편하다
      

    if(start == N){ 종료조건
            if(result == S)  합이 S가 되는 순간 count
                count++;
            return;
     }
        
        back(start+1, result+arr[start]);  지금 원소를 합에 더하는 부분
        back(start+1, result); 지금 위치의 원소는 빼고 구하는 부분
    }

 

 

 [브루트포스 코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,S,arr[];
    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());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        arr = new int[N];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            arr[i]= Integer.parseInt(st.nextToken());
        }
        
        for(int i=0;i<N;i++){
            dfs(i,arr[i]);
        }
        
        
        System.out.println(count);
        
    }
    static void dfs(int start, int sum){
        if(sum==S){
              count++;
        }
        
        for(int next=start+1; next<N; next++){
            dfs(next,sum+arr[next]);
        }
    }
}

 

 

 [해설]
     

 :  static int N, S, arr[];  수열 개수, 부분 수열 합, 수열 배열
    static int count=0;  출력할 부분수열 개수

 

 :  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<N; i++){  수열 넣기
            arr[i]=Integer.parseInt(st.nextToken());
    }
        
 :  for(int i=0;i<N;i++){  시작지점 바꿔가며  백트래킹 시작
            dfs(i,arr[i]);
    }  
        
 :  System.out.println(count);  정답 출력
    
    
 :  public static void back(int start, int sum){  start는 index 값, sum은 누적 수열 합
      

    if(sum == S)  합이 S가 되는 순간 count
          count++;
    }
        

    for(int next=start+1; next<N; next++){  다음지점 정해서 dfs 돌리
            dfs(next,sum+arr[next]);
    }
}

 

 

 

이제 풀어보러 갈께요 :)

 

 

 

 

https://www.acmicpc.net/problem/1182

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *