BOJ_9007_카누 선수 (Java, C++)

[Gold II] 카누 선수 - 9007

문제 링크

성능 요약

메모리: 120284 KB, 시간: 3992 ms

분류

이분 탐색, 중간에서 만나기, 정렬

제출 일자

2024년 12월 5일 02:28:07

문제 설명

국제 카누 경주 챔피언십 (International Canoe Sprint Championship : ICSC)가 머지 않아 개막된다. ICSC에서 인증하는 공식 보트는 C1, C2 그리고 C4로 구성되며, "C"는 카누를 그리고 숫자는 노를 젓는 사람의 수를 의미한다. 카누 경주는 잔잔한 물 위의 여러개로 구획된 직선 코스에서 이루어진다. ICSC에서는 국제 경기를 200m, 500m 그리고 1000m로 구분하고 있다.

한국 스포츠 학교(Korea Sports School : KSS)는 ICSC 의 C4 1000m 경기에 참가할 예정이다. KSS에는 같은 수의 학생으로 구성된 4개의 반을 가지며, 각 반에서 1명씩을 선출하여 경기에 참가한다. KSS에는 다수의 C4 보트를 가지고 있으며 각 보트는 선수들의 몸무게 합이 특정 값에 근사할 때 최대의 성과를 낼 수 있다. 예를 들어 특정 값이 300이고 각 반의 학생들의 몸무게가 아래와 같다고 하자.

• Class-1: 60, 52, 80, 40
• Class-2: 75, 68, 88, 63
• Class-3: 48, 93, 48, 54
• Class-4: 56, 73, 49, 75

각 반에서 차례로 60,75,93 그리고 73 학생을 선택하게 되면 몸무게 합이 301으로 300에 가장 근사하게 된다. 몇몇의 경우에는 두개의 근사값이 나올 수 있다. 예를 들어 특정 값이 200일 때, 몸무게의 합이 198과 202가 나올 수 있으며 이러한 경우에는 더 작은 값이 카누 게임 진행에 더 적합하다. 따라서 몸무게의 합이 198인 학생들이 선택받게 된다.

보트의 특정값과 학생들의 몸무게가 주어졌을때, 위의 조건을 만족하는 4명의 학생을 선택하시오.

입력

이 문제에서는 입력은 표준 입력을 사용한다. 입력의 첫 줄에는 T개의 테스트 케이스가 주어진다. 각 테스트 케이스에는 두 개의 정수 k와 n이 주어지며, k( 1 ≤ k ≤ 40,000,000)는 보트의 특정 값 그리고 n( 1 ≤ n ≤ 1,000 )은 KSS 각 반의 학생수이다.

이어지는 4개의 줄에 차례로 각 반의 학생들의 몸무게가 n개씩 주어진다. 이때 몸무게는 1에서 10,000,000까지이다.

출력

출력은 표준 출력을 이용한다. 각 테스트 케이스에 해당하는 값을 한 줄에 출력한다. 해당 줄에는 카누 선수로 지목된 학생들의 몸무게의 총합이 포함되어 있어야 한다.

문제풀이

코드

Java코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {
		new Main().solution();
	}

	public void solution() throws Exception {
		br = new BufferedReader(new InputStreamReader(System.in));
//		br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt")));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		while(T-->0) {
			st = new StringTokenizer(br.readLine());
			int k = Integer.parseInt(st.nextToken());
			int n = Integer.parseInt(st.nextToken());

			int[][] C = new int[4][n];
			
			for(int c=0; c<4; c++) {
				st = new StringTokenizer(br.readLine());
				for(int num=0; num<n; num++) {
					C[c][num] = Integer.parseInt(st.nextToken());
				}
			}			
			
			int[] C1plusC2 = new int[n*n];
			int[] C3plusC4 = new int[n*n];
			
			for(int i=0; i<n; i++) {
				for(int j=0; j<n; j++) {
					C1plusC2[i*n+j] = C[0][i] + C[1][j];
					C3plusC4[i*n+j] = C[2][i] + C[3][j];
				}
			}
			
//			C1plusC2 = Arrays.stream(C1plusC2)
//							 .sorted()
//							 .toArray();
//			C3plusC4 = Arrays.stream(C3plusC4)
//					.sorted()
//					.toArray();
			Arrays.sort(C1plusC2);
			Arrays.sort(C3plusC4);
			
			
			int res =  C1plusC2[0] + C3plusC4[0];
		
			for(int i=0; i<C1plusC2.length; i++) {
				int target = k-C1plusC2[i];
				int left = 0; int right = C3plusC4.length-1;
				
				while(left <= right) {
					int mid = left + (right - left)/2;
					int sum = C1plusC2[i] + C3plusC4[mid];
					
					if(Math.abs(k-sum) < Math.abs(k-res) || 
							(Math.abs(k-sum) == Math.abs(k-res) && sum < res )) res=sum;
					
					if(sum==k)  break;
					
					if(C3plusC4[mid] < target) left = mid+1;
					else right = mid-1;
					
				}
			}
			
			
			bw.write(String.valueOf(res)+"\n");
		}

		bw.flush();
		bw.close();
		br.close();
	}
}

---

C++코드

/**
 * Author: nowalex322, Kim HyeonJae
 */
#include <bits/stdc++.h>
using namespace std;

// #define int long long
#define MOD 1000000007
#define INF LLONG_MAX
#define ALL(v) v.begin(), v.end()

#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif

void solve() {
    int k, n;
    cin >> k >> n;
    vector<vector<int>> C(4, vector<int>(n));
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < n; j++) {
            cin >> C[i][j];
        }
    }

    vector<int> C1plusC2;
    vector<int> C3plusC4;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            C1plusC2.push_back(C[0][i] + C[1][j]);
            C3plusC4.push_back(C[2][i] + C[3][j]);
        }
    }

    sort(ALL(C1plusC2));
    sort(ALL(C3plusC4));

    int res = C1plusC2[0] + C3plusC4[0];

    for (int i = 0; i < C1plusC2.size(); i++) {
        int target = k - C1plusC2[i];
        int left = 0;
        int right = C3plusC4.size() - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int sum = C1plusC2[i] + C3plusC4[mid];

            if (abs(k - sum) < abs(k - res) ||
                (abs(k - sum) == abs(k - res) && sum < res))
                res = sum;

            if (sum == k) break;
            if (C3plusC4[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    cout << res << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int tt = 1;  // 기본적으로 1번의 테스트 케이스를 처리
    cin >> tt;   // 테스트 케이스 수 입력 (필요 시)

    while (tt--) {
        solve();
    }
    return 0;
}