[백준] 단계별로 풀어보기(단계:26, 투 포인터,JAVA)1450번, 냅색문제

문제 링크

1450번: 냅색문제

---

주의사항

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

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

---

문제 설명

---

접근 방법

투 포인터는 두 가지의 위치를 가리키는 포인터 Start, End를 이용하여 1차원 배열에 저장된 값들에 범위를 더하여 해당하는 값을 구하거나 포인터가 가리키는 값을 더해서 원하는 값을 구할 수 있도록 하는 알고리즘입니다.

 

투 포인터를 사용할 때에는 주로 정렬한 상태에서 사용합니다.

이 문제에 핵심은

1. 가방의 최대 무게 이하의 물건을 넣을 수 있는 경우의 수를 구해야 한다.

 

이 문제이름이 냅색문제이지만 냅색 알고리즘으로 처음 접근했다가 시간 초과로 틀렸습니다.

주제가 투 포인터이기 때문에 투 포인터로 작성해보려고 여러가지 방법을 써보았지만 모두 실패하였습니다.

그래서 검색을 통해 알아본 봐 중간에서 만나기 알고리즘을 사용하여 문제를 해결하는 것이었습니다.

 

중간에서 만나기란?

 

한 개의 배열을 2개의 배열의 형태로 만든 후 2개의 배열을 경우를 조합하여 모든 경우의 수를 구하는 방법입니다.

 

저는 입력값에서 N/2까지 수에서 나올 수 있는 경우의 수 배열과 N/2부터 N까지 수에서 나올 수 있는 경우의 수의 배열을 2가지 만들어 두 배열을 조합하여 모든 경우의 수를 구하였습니다.

 

예제입력 5를 살펴보면

 

N=2, C = 2

물건의 무게 = {1, 1 }

 

두 배열을 left와 right로 구분하였습니다.

left는 0~N/2 = 0~1범위의 입력값에 나올 수 있는 경우의 수는

0	1
아무것도 넣지 않았을 때

 

right는 N/2 + 1 ~ N = 2~2범위의 입력값에 나올 수 있는 경우의 수는

0	1
아무것도 넣지 않았을 때

 

left와 right의 배열을 조합하여 모든 경우의 수를 확인할 때

left가 0일 때 right값은 0, 1을 모두 조합해도 최대 무게인 2 이하이기 때문에 가능하다.

{0(0+0), 1(0+1)}

left가 1일 때 rigth값은 0, 1을 모두 조합해도 최대 무개인 2 이하이기 때문에 가능하다.

{1(1+0), 2(1+1)}

두 경우의 조합을 모두 합치면

{0(0+0), 1(0+1), 1(1+0), 2(1+1)} = 4개가 됩니다.

 

이후에 right 배열을 오름차순으로 정렬한 뒤에 이분 탐색에 UpperBound를 사용하여 left의 값에 따라 최대값을 초과하지 않는 right배열의 최대값의 범위를 얻어서 그 범위만 비교하도록 하였습니다.

 

2중 반복문을 사용할 때에는 N²의 시간복잡도가 들지만 UpperBound를 사용하면 Nlog₂N으로 더 효율적으로 문제를 해결할 수 있습니다.

 

UpperBound에 생소하시면 아래 문제를 풀고 오시면 좋을 것 같아서 링크를 남깁니다.

[백준] 단계별로 풀어보기(단계:21,이분 탐색,JAVA)10816번, 숫자 카드 2

​​

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N, C, 각 물건의 무게를 저장합니다.

2. 0~N/2 범위의 물건들의 경우의 수를 DFS를 통해서 left에 저장합니다.

3. N/2 + 1 ~ N 범위의 물건들의 경우의 수를 DFS를 통해서 right에 저장합니다.

4. right를 오름차순 정렬하여 UpperBound와 반복문을 통해 left와 right의 모든 경우의 조합을 구하였습니다.

5. 모든 경우의 조합 수를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer을 이용하여 물건의 무게값을 분리하였습니다.
• 규칙을 적용하여 범위의 소수의 합이 N이 되는 경우의 수를 구하는 cal함수를 만들었습니다.
• 이분탐색 UpperBound를 통해 left에 값에 따른 right에 최대 값이 되는 범위를 구하는 UpperBound 함수를 만들었습니다.
• right 리스트를 Collections.sort를 이용하여 오름차순 정렬을 하였습니다.
• 반복문과 UpperBound 함수를 사용하여 left와 right가 조건에 만족하는 조합의 모든 경우의 수를 구하였습니다.
• BufferedWriter에 조건 만족하는 조합의 모든 경우의 수를 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 DFS를 통해서 해당 범위의 물건들이 S이하의 무게의 합을 가지는 경우를 리스트에 저장하도록 하였습니다.
• UpperBound는 반복문을 통해 이분탐색에 UpperBound 알고리즘을 적용시켰습니다.

import java.io.*;
import java.util.*;
public class Main{
	static int[] weight;	//입력된 물건의 무게 저장 배열
	static int N,S;
    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());
    	weight = new int[N];
    	st = new StringTokenizer(br.readLine()," ");
    	for(int i=0;i<N;i++) 
    		weight[i] = Integer.parseInt(st.nextToken());
    	
    	ArrayList<Integer> left = new ArrayList<Integer>();	//0~N/2 경우의 수 저장하는 리스트
    	ArrayList<Integer> right = new ArrayList<Integer>();//N/2+1~N 경우의 수 저장하는 리스트
    	cal(0,N/2,0,left);	//DFS를 통한 left 구하기 함수 실행
    	cal(N/2,N,0,right);	//DFS를 통한 right 구하기 함수 실행
    	
    	Collections.sort(right);	//right 오름차순 정렬
    	int count = 0;		//left와 right 모든 조합의 수 저장 변수
    	for(int i=0;i<left.size();i++) {
        	//UpperBound를 이용하여 left값 + right값 <= C인 개수 구해서 count에 더하기
    		count += upperBound(right, left.get(i));
    	}
    	bw.write(count + "\n");		//결과 BufferedWriter 저장
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //이분탐색 UpperBound를 사용하여 최대 무게 이하인 경우의 수 범위 구하는 함수
    static int upperBound(ArrayList<Integer> list, int num) {
    	int start = 0;
    	int end = list.size();
    	while(start<end) {
    		int median = (start + end)/2;
    		if(list.get(median) + num <= S)
    			start = median+1;
    		else
    			end = median;
    	}
    	return start;
    }
    //DFS를 통하여 범위의 입력값 무게들의 나올 수 있는 경우의 수를 구하는 함수
    static void cal(int length, int end, int sum, ArrayList<Integer> list) {
    	if(sum > S)		//최대 무게 초과시
    		return;
    	
    	if(length==end) {	//물건 넣는 경우의 수 완성시
    		list.add(sum);
    		return;
    	}
    	cal(length+1, end, sum + weight[length], list);	//현재 물건 넣었을 때
    	cal(length+1, end, sum, list);		//현재 물건 넣지 않았을 때
    	return;	
    }
}