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

문제 링크

14225번: 부분수열의 합

---

주의사항

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

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

---

문제 설명

---

접근 방법

브루트 포스란.

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

이 문제에 핵심은

1. 수열 S의 값의 합으로 나올 수 없는 가장 작은 자연수를 결과로 출력해야 합니다.

 

 

수열 S에 대하여 최대로 나올 수 있는 값은 모든 수열의 값의 합입니다.

 

순열을 통해서 S의 값들의 합의 모든 경우를 구합니다.

 

1~최대값까지 존재하지 않는 자연수를 찾아서 가장 먼저 발견된 자연수가 가장 작은 자연수로써

 

가장 먼저 발견된 자연수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 수열 S에 대한 정보를 저장하였습니다.
• 수열 S에 나올 수 있는 모든 자연수를 구하는 cal 함수를 실행하였습니다.
• 나올 수 없는 가장 작은 자연수를 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 나올 수 있는 자연수는 1, 나올 수 없는 자연수는 0으로 저장됩니다.

 

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

public class Main {
	static int N,max=0;
	static int[] S,num;
    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
    	N = Integer.parseInt(br.readLine());
    	S = new int[N];
    	StringTokenizer st = new StringTokenizer(br.readLine()," ");
        //수열 S의 값들과 최대값을 구하였습니다.
    	for(int i=0;i<N;i++) {
    		S[i] = Integer.parseInt(st.nextToken());
    		max += S[i];
    	}
       	num = new int[max+2];	//해당 자연수가 존재하는지 확인하는 배열
    	cal(0,0);		//수열 S의 대한 순열로 모든 경우의 자연수를 만들어보는 함수 실행
        //나올 수 없는 자연수 중 가장 작은 자연수 BufferedWriter 저장
    	for(int i=1;i<=max+1;i++) {
    		if(num[i]==0) {
    			bw.write(i + "\n");
    			break;
    		}
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //수열 S의 대한 순열로 모든 경우의 자연수를 만들어보는 함수
    static void cal(int cur, int sum) {
    	for(int i=cur;i<N;i++) {
    		int temp = sum+S[i];
        	num[temp] = 1;
        	cal(i+1, temp);
    		}
    	return;
    }
}