[Softeer] [21년 재직자 대회 본선] 코딩테스트 세트 / ProblemId 630 [JAVA]

문제링크 : https://softeer.ai/practice/info.do?eventIdx=1&psProblemId=630 

Softeer

 

짝수번 째 있는 난이도를 적절히 홀수번 째 있는 난이도에 할당하면 된다.

그렇게 해서 홀수번 째에 있는 난이도 중에 가장 작은 값을 가장 크게 만드는 방법을 찾아

그 값을 정답으로 한다.

예를들면 아래와 같다

N=3 이며 난이도의 정보는 아래와 같다고 하자(입력예제1-1)

 

(1)

2 2 1 1 3

 1) 2번째 값인 2를 왼쪽에 1, 오른쪽에 1씩 할당해준 후 난이도 결과

3 0 2 1 3

 2) 4번째 값인 1을 왼쪽에 1 할당해준 후 난이도 결과

3 0 3 0 3

홀수번 째의 값은 3,3,3이다. 여기서 가장 작은 값은 3이며 이것이 정답이다.

 

(2)

 위의 예를 가지고 틀리게 할당한 방식을 확인 해보자

2 2 1 1 3

 1) 2번째 값인 2를 오른쪽에 2 할당해준 후 난이도 결과

2 0 3 1 3

 2) 4번째 값인 1을 어느쪽에 할당해주더라도 홀수번 째 값의 종류는 2, 3, 4이다. 여기서 가장 작은 값은 2이며 위의 결과보다 작은 값이므로 정답이 아니다

 

(3)

 다시 다른 방식을 해보자

2 2 1 1 3

 1) 2번째 값인 2를 왼쪽에 2 할당해준 후 난이도 결과

4 0 1 1 3

 2) 4번째 값인 1를 왼쪽에 1 할당해준 후 난이도 결과

4 0 2 0 3

 

 2n 번째의 값을 2n-1에 먼저 할당해주며, 할당하고 남은 2n번째의 값과 2n+2번째의 값을 적절히 2n+1번째 난이도에 할당한다. 다음, 남은 2n+2번째의 값과 2n+4번째의 값을 '적절히' 할당한다. 결국 '적절히' N(배열의 마지막 인덱스)-1 번째의 값을 마지막 인덱스까지 '적절히' 할당 해주면 된다

 

 '적절히' 라는 값을 정말 '잘' 설정해주면 문제는 해결된다.

 

할당값을 모두 적용해보기에는 10^12라는 값이 너무 크다.

 

2n번째의 값을 반복적으로 끝까지 할당해보면서 2k 번째의 값을 할당할 때 할당받은 2k-1의 값과 2k+1의 값 중 어느 하나가 이전에 할당받은 값보다 작다면 그 할당이 최선이거나 이전에 어느 2k(1<=k<=N-1)에서 해준 할당을 덜 해주었으면 해결되었을 문제이다.(위 3번째 예시와 같다. 2번째 값인 2 중 왼쪽에 1만 할당해줬으면 3번째(가운데) 값이 3이 되었을 것이다.

 

 

그래서 어떻게 할 것인가??

이러한 문제를 풀 때 입력변수의 범위는 정말 큰 힌트가 된다.

cidi의 값은 10^12이므로 이 값을 적절히 할당하기 위해서는 수학적 계산 혹은 log(N)의 탐색을 떠올리면 된다. 

 

2n번째의 값에게 할당받아 설정될 2k-1(1<=k<=N)난이도의 목표 값을 X라 하자

2k-1번째 값에서 목표 값 X를 할당받는 데 실패했다면 배열의 뒷부분의 모든 원소에서 목표 값 할당에 성공했더라도 X는 정답이 될 수 없다. 

모든 원소에서 목표 값 X를 할당받는 데 성공했다면 모든 2k번째의 값들은 0보다 크거나 같을 것이다. (할당해주고 남거나 모두 할당해주었기 때문) -> 목표 값을 너무 낮게 설정 했다면 많이 남을 것이다.

 

목표 값 X를 이분법으로 설정 해준다면 log(10^12)이며 배열의 길이는 10^5이므로 이 문제를 이분탐색으로 푼다면 시간 내에 해결될 것이다. 

목표 값 X를 설정해준 후 2k번째 값을 할당하는 문제는 왼쪽(2k-1)부터 X값까지 먼저 할당하고 남은 값을 오른쪽(2k+1)에 모두 할당하는 방식으로 하면 된다. 이유는, 왼쪽 값은 X값 이상이 되어야 하나 과하게 할당해줄 필요가 없어서 이며, 남은 2k번째 값을 굳이 남길 필요가 없어서 남은 값을 오른쪽에 모두 할당해주는 것이다. 

 

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

public class Main {
    public static int N,T;
    public static long arr[];

    public static void main(String[] args)throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        T = Integer.parseInt(st.nextToken());

        for(int i=0;i<T;i++){
            arr = new long[2*N-1];
            st = new StringTokenizer(br.readLine());
            long ans = 0;
            long left = 0;
            long right = 0;
            for(int j=0;j<2*N-1;j++){
                arr[j] = Long.parseLong(st.nextToken());
                if(j%2==1){
                    right = Math.max(right,Math.max(arr[j]+arr[j+1],arr[j]+arr[j-1]));
                }
            }
            while(left<=right){
                long mid = (left+right)/2;
                boolean suc = true;
                long indo = 0; //2n에서 2n-1로 할당하고 남은 값 (초기 0)
                for(int j=1;j<2*N-1;j+=2){
                    long num = indo + arr[j-1]; // 2n번째 값
                    if(num<mid){
                        if(mid-num > arr[j]){ //왼쪽에 할당해도 목표치보다 낮은 경우
                            suc = false;
                            break;
                        }else{
                            indo = arr[j] - (mid-num);//왼쪽에 할당 후 갱신
                        }
                    }else{
                        indo = arr[j]; //할당해줄 필요가 없는 경우 
                    }
                }
                if(arr[2*N-2]+indo<mid){ //마지막 원소 체크
                    suc = false;
                }
                if(suc){
                    left = mid+1;
                    ans = mid;
                }else{
                    right = mid-1;
                }
            }
            System.out.println(ans);
        }
    }
}