Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

26. 투 포인터

투 포인터 알고리즘과 meet in the middle 알고리즘을 배워 봅시다.

Java / Python

5. 소수의 연속합

1450번

Meet in the middle 알고리즘을 배우는 문제

이번 문제는 N개의 물건을 가방에 넣는 방법의 수를 구하는 프로그램을 작성하는 문제입니다.

투 포인터 알고리즘을 이용해, 절반으로 나누어풀었습니다.

• Java

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

public class Main {  
	static int N, C;
	static int[] arr;
    
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));   
		StringTokenizer st = new StringTokenizer(br.readLine());
        
		N = Integer.parseInt(st.nextToken()); 
		C = Integer.parseInt(st.nextToken()); 
        
		st = new StringTokenizer(br.readLine());
		arr = new int[N];
		for(int i = 0; i < N; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}        

		ArrayList<Integer> left = new ArrayList<Integer>();
		ArrayList<Integer> right = new ArrayList<Integer>();
        
		dfs(0, N/2, 0, left);
		dfs(N/2+1, N-1, 0, right);
		
		Collections.sort(left);
		Collections.sort(right);
        
		int result = 0;
		int e = right.size() - 1;
		for(int i = 0; i < left.size(); i++){
			while(e >= 0 && left.get(i)+right.get(e) > C){
				e--;				
			}
			result += e+1;
		}
		bw.write(result + "\n");
        
		bw.flush();
		br.close();
		bw.close();
	}
	public static void dfs(int st, int end, int sum, ArrayList<Integer> list){
		if(sum > C) return;
		if(st > end) {
			list.add(sum);
			return;
		}
		dfs(st+1, end, sum, list);
		dfs(st+1, end, sum + arr[st], list);
	}
	
}

• Python

import sys

N, C = map(int, sys.stdin.readline().split())
weight = list(map(int, sys.stdin.readline().split())) 
left = weight[:N // 2] 
right = weight[N // 2:] 
lsum = [] 
rsum = [] 

def bruteforce(st, end, warr, sumarr): 
    if st >= len(warr): 
        sumarr.append(end) 
        return     
    bruteforce(st + 1, end, warr, sumarr)    
    bruteforce(st + 1, end + warr[st], warr, sumarr) 
 
def binarysearch(start, end, arr, target): 
    while start < end: 
        mid = (start + end) // 2 
        if arr[mid] <= target: 
            start = mid + 1 
        else: 
            end = mid 
    return end 

bruteforce(0, 0, left, lsum) 
bruteforce(0, 0, right, rsum) 
rsum.sort() 

result = 0 
for i in lsum: 
    if C - i >= 0: 
        result += binarysearch(0, len(rsum), rsum, C - i) 
    
print(result)