[백준 / BOJ] 17383 옥토끼는 통신교육을 풀어라!!

문제

출처 : https://www.acmicpc.net/problem/17383

17383번: 옥토끼는 통신교육을 풀어라!!

옥토끼는 두개의 문제를 한번에 풀수있다. 

N개의 문제가 주어질때, 문제를 푸는 시간사이의 공백을 최소화하는 시간을 구하는 문제다.

---

풀이

결정문제로 풀은 문제였다.

 

Ni가 최대 10억이고, 완전탐색으로 풀경우, 최소 max(Ni)*(a), (a>N)시간복잡도가 나와서, 항상 시간초과가 나온다.

위의 식 N*(a)의 시간을 줄이는 방법은 다음과 같다.

 

1. N 

N이 의미하는것은, 모든 문제를 T시간 이내로 줄일수 있는가? 이다.

완전탐색으로 풀경우, 1~max(Ni)만큼의 시간복잡도가 나오지만, 문제에서 원하는 것은 문제를 푸는 두 간격 사이의 거리의 최댓값을 최소로 하는것이다.

따라서, "모든 문제를 푸는 간격을 T시간 이내로 할수있는가?" 라는 질문에 답하는 결정문제로 바꿈으로써 시간복잡도를 

N -> log(N)으로 줄일수있다.

 

2. (a)

(a)는 모든 문제를 T시간 이하로 만들수있는지 확인하는 과정을 의미한다.

완전탐색으로 풀경우, N^2이 나오기 때문에, 최적화를 해줘야하는데, 그 방법은 다음과 같다.

 

접은글은 TLE설명이에요 관심없는 사람은 패스하세요. 이게 왜 TLE?

유니온파인드에 이분탐색으로 구현해서, (a)를 O(N + NlogN)시간으로 만들었다. 아슬아슬하게 통과될줄 알았는데, 시간초과가 나왔다. 추가시간이 없는 문제를 Java로 풀어서 그런거 같은데, 혹시나 컴파일 과정이 빠른, C언어같은 언어로 문제를 푸는사람이 이 글을 본다면 한번 시도해봐도 좋을것 같다.

 

로직을 간략히 설명하면, 선택할 수 있는 문제를 찾는 과정을 이분탐색으로 진행한다. 이때, 한번 탐색한 문제를 중복해서 선택할 수 없으니, 유니온파인드로 경로를 최적화 시켜줬다.

 

소스코드

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

public class Main{
    
    public static void main(String[] args){
        Solve solve = new Solve();
		solve.run();
    }
    
}

class Solve{
	
	private int N, maxValue;
	private int[] arr;
	private int[][] par;
	private int parIdx;
	
	public void run(){
		input();
		System.out.println(getMinimumTaskTime());
	}
	
	private void input(){
		try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))){
			String[] read = br.readLine().split(" ");
			this.N = Integer.parseInt(read[0]);
			read = br.readLine().split(" ");
			arr = new int[N];
			par = new int[N+1][32];
			for(int i = 0; i < N; i++) arr[i] = Integer.parseInt(read[i]);
			for(int i = 0; i < 32; i++) for(int j = 0; j <= N; j++) par[j][i] = j;
			Arrays.sort(arr);
			maxValue = arr[N-1] == arr[0] ? arr[N-1] : Math.max(arr[N-1]/2, arr[0]);
		}catch(IOException IOE){}
	}
	
	// logic
	
	private int getMinimumTaskTime(){
		int min = 0, max = maxValue;
		int ret = max;
		while(min <= max){
			int taskTime = (min + max) / 2;
			if(doTask(taskTime)){
				max = taskTime-1;
				ret = taskTime;
			}
			else min = taskTime+1;
		}
		return ret;
	}
	
	private boolean doTask(int taskTime){
		parIdx++;
		long cnt = 0, p1 = 0, p2 = 0;
		while(cnt < N){
			int selectIdx = taskIdx(p1, p2, taskTime*(cnt+1));
			int unionIdx = unionFind(selectIdx, parIdx);
			if(unionIdx >= N || (p1 + arr[unionIdx] > taskTime*(cnt+1) && p2 + arr[unionIdx] > taskTime*(cnt+1))) return false;
			
			if(p1 >= p2){
				if(p1 + arr[unionIdx] <= taskTime*(cnt+1)) p1 = taskTime*(cnt+1);
				else if(p2 + arr[unionIdx] <= taskTime*(cnt+1)) p2 = taskTime*(cnt+1);
			}
			else{
				if(p2 + arr[unionIdx] <= taskTime*(cnt+1)) p2 = taskTime*(cnt+1);
				else if(p1 + arr[unionIdx] <= taskTime*(cnt+1)) p1 = taskTime*(cnt+1);
			}
			
			par[selectIdx][parIdx] = par[selectIdx+1][parIdx];
			unionFind(selectIdx, parIdx);
			cnt++;
		}
		return true;
	}
	
	private int unionFind(int idx, int parIdx){
		if(par[idx][parIdx] == idx) return idx;
		return par[idx][parIdx] = unionFind(par[idx][parIdx], parIdx);
	}
	
	private int taskIdx(long p1, long p2, long taskTime){
		int left = 0, right = N-1;
		int ret = 0;
		while(left <= right){
			int idx = (left + right) / 2;
			int unionIdx = unionFind(idx, parIdx);
			if(unionIdx < N && (arr[unionIdx] + p1 <= taskTime || arr[unionIdx] + p2 <= taskTime)){
				left = idx+1;
				ret = idx;
			}
			else right = idx-1;
		}
		return ret;
	}
	
}

 

 

이 아래부터는 (a)를 O(N)으로 줄이는 풀이이다.

조건

문제를 잘 생각해보면 다음 3가지 조건들을 유추할수있다.

 

조건 1. 모든 문제를 푸는 간격을 T시간 이내로 할 수 있는가? 이 말은 곧, 모든 문제를 T(i)분기점마다 끝낼수있는가? 로 바꿀수있다. 

T(i)분기점은 다음을 의미한다.

T = 5일때,

T(1) = 5

T(2) = 10

T(3) = 15

T(4) = 20

T(5) = 25

T(6) = 30

.

.

.

 

조건 2. 두개의 문제푸는 시작점을 각각 p1, p2라고 하자. p1에서 분기점 T(i)미만으로 끝낼수 있는 문제라도 T(i)에 딱 맞춰서 끝내는것이 p2시작점에게 더 많은 선택지를 줄 수 있다.(그 반대도 마찬가지임)

 

따라서, T미만으로 풀 수 있는 문제더라도 늦게시작해서 T에 맞춰 끝내는것이 항상 이득이다.

 

예를들어 설명하면

 

분기점 T = 5

문제풀이시간은 각각 4 5 6 7 8 10 이라고 하자.

 

시작점 p1에서 첫번째 문제를 0시간부터 풀기 시작해서, 4시간에 끝낸다면, 두번째 p2에서 올수있는 문제의 범위는 아래와 같다.

5 6 7 8  (문제 <= 9) 

푸는데 10시간이 걸리는 문제는 p2에서 시작할 수 없음을 알수있다.

 

하지만, p1에서 첫번째 문제를 1시간부터 풀기 시작해서 5시간에 끝낸다면, 두번째 p2에서 올수있는 문제의 범위는 아래와 같다.

5 6 7 8 10 (문제 <= 10)

푸는데 10시간이 걸리는 문제까지 p2에서 시작할 수 있고, 이때도 모든 문제를 5시간안에 풀 수 있음을 알수있다. 즉, 답에 영향을 미치지 않을수 있더라도, 매 경우마다 선택의 폭을 넓혀준다.

 

조건 3. 조건 2에 따라서, 문제를 최대한 늦게풀어 T시간에 맞추는것이 항상 이득이므로, p1에서 하나의 문제를 풀었을때, 반대편, p2에는 T시간만큼의 여유가 생긴다. (반대도 마찬가지)

 

예를들어 설명해보면  

초기 p1과 p2의 시작점은 각각 (0, 0)이다.

p1에서 5시간 짜리 문제를 풀었다면, p1과 p2의 시작점은 다음과 같이 변한다.

(5, 0)

이때, p1과 p2의 차는 5만큼(T)이 난다.

 

p2에서 5시간 짜리 문제를 풀기 시작했을때, 조건 2번에 의하여 최대한 늦게 시작하여 10시간 이내로만 풀면된다. 따라서, p1과 p2의 시작점은 다음과 같이 변한다.

(5, 10)

 

로직

조건 2와 조건 3에 의하여, 다음 로직을 생각할 수 있다.

 

- 문제를 푸는 시간이 저장된 배열을 arr, i번째 문제를 푸는데 걸리는 시간을 arr[i]

- 모든 문제를 T시간 안에 풀수있는가?

- 반대편의 의미하는것은, 현재 내가 보고있는 위치가 p1이라면, 반대편은 p2이다.

 

1. arr[i] <= T * 1 이라면, arr[i]를 풀기 위해서 반대편 에는 arr[i] <= T * 0 이여야 한다.

즉, arr[i] <= T * 1 일때는, 어떠한 조건없이 항상 풀수있다.

 

2. arr[i] <= T * 2 이라면, arr[i]를 풀기 위해서 반대편 에는 arr[i] <= T * 1 이여야 한다.

즉, arr[i] <= T * 2 를 풀기 위해서는, arr[i] <= T*1이 적어도 하나는 있어야한다.

 

3. arr[i] <= T * 3 이라면, arr[i]를 풀기 위해서 반대편 에는 arr[i] <= T * 2 이여야 한다.

즉,  arr[i] <= T * 3을 풀기 위해서는, arr[i] <= T*1이 적어도 두개는 있어야한다.

.

.

.

 

이때, 조건 3에 의해서, 하나의 문제를 풀었을때, arr[i] <= T * 1 이 항상 하나씩 생긴다는것을 알수있다. 따라서, 위 로직을 다음과 같이 바꿀 수 있다.

1. arr[i] <= T * 1 이라면, arr[i]를 풀기 위해서 반대편 에는 arr[i] <= T * 0 이여야 한다.

즉, arr[i] <= T * 1 일때는, 어떠한 조건없이 항상 풀수있다.

 

2. arr[i] <= T * 2 이라면, arr[i]를 풀기 위해서 반대편 에는 arr[i] <= T * 1 이여야 한다.

즉, arr[i] <= T * 2 를 풀기 위해서는, arr[i] <= T*1이 적어도 0개는 있어야한다. (반대편에서 문제를 풀었기 때문에 항상 한개는 갖고 시작하므로,)

 

3. arr[i] <= T * 3 이라면, arr[i]를 풀기 위해서 반대편 에는 arr[i] <= T * 2 이여야 한다.

즉,  arr[i] <= T * 3을 풀기 위해서는, arr[i] <= T*1이 적어도 1개는 있어야한다.  (반대편에서 문제를 풀었기 때문에 항상 한개는 갖고 시작하므로,)

.

.

.

 

최종 핵심 코드를 보면 다음과 같다.

	private boolean doTask(int taskTime){
		System.out.println("\ntaskTime : " + taskTime);
		if(arr[0] > taskTime) return false;
		int prime = 0;
		int remain = 1;
		for(int i = 1; i < N; i++){
			if(arr[i] <= taskTime*1){
				prime++;
				continue;
			}
			int space = arr[i] / taskTime + (arr[i] % taskTime > 0 ? 1 : 0) - 2;
			if(space > prime) return false;
			prime -= space;
		}
		return true;
	}

위 코드는 모든 문제를 taskTime안에 풀 수 있는지 확인후, 풀 수 있다면 true 아니라면 false를 반환한다.

 

 

통과될거라고 예상했던 코드가 TLE가 나와서 상당히 애 먹었던 문제다. 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/17383%20%EC%98%A5%ED%86%A0%EB%81%BC%EB%8A%94%20%ED%86%B5%EC%8B%A0%EA%B5%90%EC%9C%A1%EC%9D%84%20%ED%92%80%EC%96%B4%EB%9D%BC!!/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃