[백준(Baekjoon)][자바(java)] 2143: 두 배열의 합 / 이분 탐색

 

www.acmicpc.net/problem/2143

2143번: 두 배열의 합

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
	
	public static int lower_bound( int val, int start, int end, int a[] ) {	
		// 배열 a에서 k값이 처음으로 나타나는 인덱스
		while( start < end ) {
			int mid = (start+end)/2;
			if( a[mid] >= val )		
				end = mid;
			else start = mid+1;
		}
		return end;
	}
	
	public static int upper_bound( int val, int start, int end, int a[] ) {	
		// 배열 a에서 k보다 큰 값이 처음으로 나타나는 인덱스
		while( start < end ) {
			int mid = (start+end)/2;
			if( a[mid] > val )	
				end = mid;
			else start = mid+1;
		}
		return end;
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int t = Integer.parseInt( br.readLine() );
		int n_a = Integer.parseInt( br.readLine() );
		int a[] = new int[n_a], i, j;
		StringTokenizer st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n_a; i++ )
			a[i] = Integer.parseInt( st.nextToken() );
		int n_b = Integer.parseInt( br.readLine() );
		int b[] = new int[n_b];
		st = new StringTokenizer( br.readLine() );
		for( i = 0; i < n_b; i++ )
			b[i] = Integer.parseInt( st.nextToken() );
		br.close();
		
		int l_a = 0, l_b = 0;
		for( i = 1; i <= n_a; i++ )
			l_a += i;
		for( i = 1; i <= n_b; i++ )
			l_b += i;
		int a_ss[] = new int[l_a];	// sub sum
		int b_ss[] = new int[l_b];	
		int idx = 0;
		int ss;
		for( i = 0; i < n_a; i++ ) {
			ss = 0;
			for( j = i; j < n_a; j++ ) {
				ss += a[j];
				a_ss[idx++] += ss;
			}
		}
		idx = 0;
		for( i = 0; i < n_b; i++ ) {
			ss = 0;
			for( j = i; j < n_b; j++ ) {
				ss += b[j];
				b_ss[idx++] += ss;
			}
		}
		
		Arrays.sort( b_ss );
		
		long cnt = 0;
		int val, ub, lb;
		for( i = 0; i < l_a; i++ ) {
			val =  t - a_ss[i];
			ub = upper_bound( val, 0, l_b, b_ss );
			lb = lower_bound( val, 0, l_b, b_ss );
			cnt += ub - lb;
		}
		
		System.out.println( cnt );
		
	}
}

 

* 이분탐색, 누적 합

- 배열 a, b 각각의 부분합을 구해 a_ss, b_ss 생성 ( sub sum )

- b_ss 정렬 후 이분탐색 하면서 t - a_ss[i] 를 찾음

  upper bound, lower bound를 구해 차이를 cnt에 더함