백준 9007번 : 카누 선수

문제 : https://www.acmicpc.net/problem/9007

 

출 처 : 한겨례 신문 / [아하 스포츠] ‘알쏭달쏭’ 카누, 카약, 조정…뭐가 다를까?

 

카누 선수입니다. 경주에서는 얼마나 빠르게 결승선에 도달했는지 시간이 중요합니다. 하지만 분명 완주했다는 것도 박수를 받아야 합니다. 하지만 코테에서는 그렇지 않습니다. 정말 슬픈 일이죠. 시간이 중요합니다. 

 

N명의 학생이 있는 4개의 반에서 한명씩 뽑아 그 합이 K와 가장 가까운 값을 구해야 합니다. 

 

최적화 문제입니다. 3초라는 낭낭한 시간에 혹시나 하는 마음으로 모든 경우를 확인하면 시간초과가 반겨줍니다. 

 

처음에 제가 생각한 방법은 방문 숫자에 대한 최적화 방법이었습니다. 

 

Set <>[4]을 사용하여, 각 단계에서 이미 방문한 적 있는 숫자를 체크하여 중복을 제거하는 방향으로 구현했었습니다. 

메모리 초과가 나왔습니다. 

메모리 초과가 생기는 원인은 굉장히 많지만, 그중 제가 고칠 수 있는 것은 별로 없습니다. 1. 재귀함수의 무한 루프 2. while 문의 무한 반복, 3. que의 너무 많은 요소를 넣을 경우 정도가 있습니다. 그 외에는 정말 지엽적인 이유들이 존재하지만 저는 위 3개의 경우가 아니면 접근 방법을 다르게 생각합니다.  

 

그다음 생각한 방법은 이분탐색을 이용하는 방법입니다. 

 

하지만 지금 문제의 사분? 탐색의 상황을 이분탐색으로 바꿔줘야 하는 부분이 쉽지 않았습니다.

그 방법은 1(3) 반과 2(4) 반의 합을 통해 N^2의 길이를 갖는 배열을 만들고 이분탐색을 실시하면 됩니다. 이분탐색의 시간복잡도는 O(logN) 이니까, 위 과정의 전체 시간복잡도는 O(N^2 logN^2) 이 됩니다 

 

문제의 형태를 합쳐서 이분탐색이 적용하기 쉬운 형태로 바꿔주는 부분이 이 문제의 하이라이트인 것 같습니다. 

 

+ 이분탐색의 종료조건을 늘 헷갈리는데, 이 부분을 조금 더 생각해 보겠습니다. 

int l = 0;
int r = n;
while(l<r){
    int m = (l+r)/2;
    if(value>targetNum){
        r = m-1;
    }else {
        l = m+1;
    }
}

 

위와 같은 구조에서 탐색의 종료조건을 l <r로 설정하면 맨 마지막 값을 탐색하지 못하는 경우가 발생합니다. 

 

예 1)

arr = 1,2,3,4

l = 0, r = 3, m =1

l = 0 , r = 0  탐색 종료!

---

 만일 같은 값이 여러 개인 경우 Upper Bound를 찾고 싶은 경우 아래와 같이 if 문을 작성

int l = 0;
int r = n;
while(l<=r){
	int m = (l+r)/2;
    if(m >= target){
    	l = m +1;
    }else{
    	r = m-1;
    }
}

 

- 코드

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 void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<t;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int targetNum = Integer.parseInt(st.nextToken());
            int studentNumber = Integer.parseInt(st.nextToken());
            int[][] classInfo = new int[4][studentNumber];
            int[] sum12 = new int[(studentNumber) * (studentNumber)];
            int[] sum34 = new int[(studentNumber) * (studentNumber)];
            for(int j=0;j<4;j++){
                st = new StringTokenizer(br.readLine());
                for(int k=0;k<studentNumber;k++){
                    classInfo[j][k] = Integer.parseInt(st.nextToken());
                }
            }
            for(int j=0;j<studentNumber;j++){
                for(int k=0;k<studentNumber;k++){
                    sum12[studentNumber*j+k] = classInfo[0][j]+classInfo[1][k];
                    sum34[studentNumber*j+k] = classInfo[2][j]+classInfo[3][k];
                }
            }
            Arrays.sort(sum12);
            Arrays.sort(sum34);
            int ans = Integer.MAX_VALUE;
            int diff = Integer.MAX_VALUE;
            loop1:
            for(int j=0; j<studentNumber * studentNumber;j++){
                int l = 0;
                int r = (studentNumber * studentNumber)-1;
                while(l<=r){
                    int m = (l+r)/2;
                    int value = sum12[j] +sum34[m];
                    if(value == targetNum) {
                        ans = value;
                        break loop1;
                    }
                    if(Math.abs(targetNum-value) == diff){
                        ans = Math.min(ans,value);
                    }else if(Math.abs(targetNum-value) < diff){
                        diff = Math.abs(targetNum-value);
                        ans = value;
                    }
                    if(value>targetNum){
                        r = m-1;
                    }else {
                        l = m+1;
                    }
                }
            }
            sb.append(ans).append('\n');
        }
        System.out.print(sb);
    }
}