[백준] code.plus(브루트포스-비트마스크,JAVA)1182번, 부분수열의 합

문제 링크

1182번: 부분수열의 합

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

이 문제에 핵심은

1. N개의 정수와 만들어야 하는 합 S가 주어집니다.

2. N개의 정수의 합이 S가 되는 경우의 수를 구하여 출력합니다.

 

배열

 

num: N개의 숫자를 저장할 배열

 

재귀문과 num배열을 이용하여 N개의 정수로 만들 수 있는 합을 모든 경우의 수를 구해서 S와 같은 경우를 찾았습니다.

 

문제에 해결알고리즘은

1. 정수 N개 받습니다.

2. 정수의 합이 나오는 모든 경우의 수를 확인하여 S의 값이 나올 때마다 +1을 합니다.

3. 모든 경우의 수 확인 후 S의 합이 나오는 경우의 수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 통해 N개의 정수를 저장하였습니다.
• 부분 수열의 합이 S가 되는 경우의 수를 구하는 sum 함수를 만들었습니다.
• BufferedWriter에 합이 S가 되는 경우의 수를 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• sum은 재귀와 num[]을 이용하여 합이 S와 같은 수열을 탐색하였습니다.
• S와 동일한 경우를 탐색했을 때 result에 +1을 해주었습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int[] num;	//N개 숫자 저장 배열
	public static int N,S,result=0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화----------
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	N = Integer.parseInt(st.nextToken());
    	S = Integer.parseInt(st.nextToken());
    	num = new int[N];
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<N;i++) 
    		num[i] = Integer.parseInt(st.nextToken());
        //시작 값 지정 및 함수 실행
    	for(int i=0;i<N;i++) {
    		sum(i+1,num[i]);
    	}
    	bw.write(result + "\n");	//경우의 수 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    }
    //-----------부분 수열의 합이 S가 되는 경우의 수 구하는 함수----------
    public static void sum(int length, int cur) {
    	if(cur == S) {
    		result++;		//합이 S일 때
    	}
    	for(int i=length;i<N;i++) {
    		sum(i+1, cur + num[i]);		//재귀 발동
    	}
    	return;
    }
}