[백준] code.plus(브루트포스 - 기타,JAVA)1208번, 부분수열의 합 2

문제 링크

1208번: 부분수열의 합 2

---

주의사항

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

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

---

문제 설명

---

접근 방법

브루트 포스란.

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

이 문제에 핵심은

1. 입력된 수열에 부분 수열의 합이 S가 되는 개수를 결과로 출력합니다.

 

처음에 간단한 브루트 포스로 접근하였지만 시간 초과가 발생하였습니다.

 

수열을 반으로 나누어서 각 수열에 대하여 부분 수열의 합을 구한 뒤 비교하여 횟수를 구하였습니다.

 

예제입력1

 

수열의 값

-7

-3

-2

5

8

 

반으로 나누면

 

수열1

-7

-3

나올 수 있는 부분 수열의 합 : -10, -7, -3, 0

 

수열 2

-2

5

8

나올 수 있는 부분 수열의 합 : -2, 0, 3, 5, 6, 8, 11, 13

 

두 수열의 값들의 합이 S가 되는 개수를 구한다.

(-3, 3), (0, 0) = 2개

 

※ (0, 0)은 둘 다 원소를 선택하지 않은 값으로써 제외되어 1개가 결과로 출력된다.

(0, 0)가 원소를 선택하지 않는 쌍으로 결과에 선택되는 것은 S = 0일 때이기 때문에

S = 0일 때에는 결과에 -1을 해주어야 한다.

 

두 수열의 합을 구할 때에 간단한 브루트 포스로 구현해서 실행하였지만 시간 초과가 다시 발생하였습니다.

 

두 수열의 값들을 오름차순으로 정렬한 뒤에 두 포인터 알고리즘을 이용하여 횟수를 구하였습니다.

 

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 수열에 대한 정보를 저장하였습니다.
• 수열을 반으로 나누어 각 수열의 부분 원소들의 모든 경우의 합을 구하는 cal함수를 실행하였습니다.
• 두 포인터를 이용하기 위해서 오름차순 정렬을 하였습니다.
• 나뉜 두 수열의 값의 합이 S가 되는 개수를 구하는 compare함수를 실행하였습니다.
• S가 0인 경우에 두 수열에 아무것도 선택되지 않았다는 (0,0)이 개수에 포함되어 -1을 진행합니다.
• S가 나오는 개수를 BufferedWriter에 저장합니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal함수는 재귀를 통해서 나뉘어진 수열에 모든 경우의 합을 ArrayList<>에 저장하였습니다.
• compare함수는 두 포인터 알고리즘을 이용하여 합이 S가 되는 개수를 구하였습니다.

 

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

public class Main{
	static int N,S;
	static int[] num;	//입력되는 수열
	static ArrayList<Integer> leftlist = new ArrayList<>();	//반으로 나뉜 왼쪽 수열
	static ArrayList<Integer> rightlist = new ArrayList<>();	//반으로 나뉜 오른쪽 수열
	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());
		
		cal(0,N/2,0,leftlist);	//반으로 나눈 왼쪽 수열의 부분 합 모든 경우 구하기
		cal(N/2,N,0,rightlist);	//반으로 나눈 오른쪽 수열의 부분 합 모든 경우 구하기
		
        	//오름차순 정렬
		Collections.sort(leftlist);	
		Collections.sort(rightlist);
		long result = compare();	//두 수열의 합이 S가 되는 경우 구하기
		
        	//S=0일 때 (0,0)인 아무 값도 선택되지 않는 경우가 결과에 포함되어 결과-1을 진행합니다.
		if(S==0)
			result -= 1;
		
		bw.write(result + "\n");	//횟수를 BufferedWriter 저장
		bw.flush();		//결과 출력
		bw.close();
		br.close();
	}
    	//두 수열의 값의 합이 S가 되는 개수를 구하는 함수
	static long compare() {
		long count = 0;		//S가 되는 개수
        	//두 포인터 설정
		int leftIdx = 0;	//왼쪽 수열 index
		int rightIdx = rightlist.size()-1;	//오른쪽 수열 index
		while(true) {
			if(leftIdx==leftlist.size() || rightIdx < 0)	//범위 벗어날 경우
				break;
			int left = leftlist.get(leftIdx);	//현재 왼쪽 수열 합의 값
			int right = rightlist.get(rightIdx);	//현재 오른쪽 수열 합의 값
			int temp = left + right;
			if(temp==S) {		//합이 S인 경우
				long leftCount = 0;
                		//각 수열에 동일한 값이 존재하는 경우
				while(leftIdx<leftlist.size() && leftlist.get(leftIdx)==left) {
					leftCount++;
					leftIdx++;
				}
				long rightCount = 0;
				while(rightIdx>=0 && rightlist.get(rightIdx)==right) {
					rightCount++;
					rightIdx--;
				}
				count += (leftCount * rightCount);	//모든 횟수 추가
			}
			if(temp>S) 	//합이 S보다 큰 경우
				rightIdx--;
			if(temp<S)	//합이 S보다 작은 경우
				leftIdx++;
		}
		return count;
	}
    	//나뉜 수열에 대하여 부분 원소들의 모든 합을 구하는 함수
	static void cal(int start, int end, int sum, ArrayList<Integer> list) {
		if(start==end) {
			list.add(sum);
			return;
		}
		cal(start+1, end, sum, list);
		cal(start+1, end, sum+num[start],list);
	}
}