1508 레이스

 

 

가장 가까운 심판의 거리가 최대가 될 곳을 파악해야 한다.

 

11 2 4
0 5 10 11

이 예제에서 생각해보면,

최대 심판을 2곳에 위치시킬 수 있다.

 

1) 첫 번째 심판의 위치

일단, 문제에서 정답이 여러개일 경우 사전순으로 가장 늦는 것을 출력하라고 했으므로,

일단 0의 위치에 심판을 위치시킨다.

 

 

심판 위치 상태

1

 

2) 두 번째 심판의 위치  

최대 2곳에 심판을 위치시킬 수 있으므로 한 곳을 더 찾아야 한다.

 

2-1) 5에 위치 시킴

 

심판 위치 상태

1 1 0 0

 

-> 가장 가까운 심판의 거리는 5-0 = 5 이다.

 

2-2) 10에 위치 시킴

 

심판 위치 상태

1 0 1 0

 

-> 가장 가까운 심판의 거리는 10-0 = 10 이다.

 

2-3) 11에 위치 시킴

 

심판 위치 상태

1 0 0 1

 

-> 가장 가까운 심판의 거리는 11-0 = 11 이다.

 

즉, 우리가 찾아야 하는 위치는 11이다.

 

 

알고리즘 설명

 

이분탐색을 사용하면 된다.

즉, 우리는 심판들이 최대한 멀리 떨어져 있게 위치시켜야 한다. 

 

그러면 일단 이분탐색으로

left = 0, right = N(11)로 정하고

 

1) 맨 처음 심판의 위치

0에 위치한다. 

 

심판 위치 상태

1 

 

2) 두번째 심판이 위치할 곳 

<1>

그러면 그 다음에 위치할 심판을 찾아야 하는데,

mid = (left + right)/2 = 5 이다 (int형식)

 

심판이 위치할 수 있는 곳에서 앞에서부터 

0의 위치와 그 다음 5의 위치가 만약 5보다 크거나 같으면 그곳에 심판을 위치시킨다.

심판 위치 상태

1 1

 

-> 심판이 최대 2곳에 위치시킬 수 있는데,

이미 위치 되었으므로 

일단 멈춘다.

 

심판 위치 상태

1 1 0 0 

 

그런데 우리는 최대한 심판이 멀리 떨어져 있게 해야하므로,

mid 값을 올려야 한다.

-> left = mid + 1 = 6

 

그 후 다시 심판이 위치할 곳을 찾아본다. 

 

<2>

mid = (left + right)/2 = (6 + 11)/2 = 8 이다 (int형식)

그러면 이 경우 0과 5는 8보다 작으므로, 0 다음 10에 심판이 위치한다.

 

심판 위치 상태

1 0 1 0 

 

이 경우도 더 심판이 멀리 떨어져 있게 할 수 있으므로

mid 값을 올려야 한다.

-> left = mid + 1 = 9

 

<3>

mid = (left + right)/2 = (9 + 11)/2 = 10 이다 (int형식)

그러면 이 경우 0과 5는 10보다 작으므로, 0 다음 10에 심판이 위치한다.

 

심판 위치 상태

1 0 1 0 

 

이 경우도 더 심판이 멀리 떨어져 있게 할 수 있으므로

mid 값을 올려야 한다.

-> left = mid + 1 = 11

 

<4>

mid = (left + right)/2 = (11 + 11)/2 = 11 이다 (int형식)

그러면 이 경우 0과 5, 0과 10은 11보다 작으므로, 0 다음 11에 심판이 위치한다.

 

심판 위치 상태

1 0 0 1 

 

이제 left = right 이고 더 이상 멀리 떨어지게 할 수 없어서

이 경우가 답이 된다. 

 

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



public class Main {
	
    public static void main(String[] args)  throws IOException {
  
    	
    	   BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
           StringTokenizer st = new StringTokenizer(br.readLine(), " ");
       	   int N = Integer.parseInt(st.nextToken());
       	   int M = Integer.parseInt(st.nextToken());
       	   int K = Integer.parseInt(st.nextToken());
       	   
       	   int input[] = new int [K];
       	   st = new StringTokenizer(br.readLine(), " ");
       	   for(int i=0; i<K; i++) {
       		   input[i] = Integer.parseInt(st.nextToken());
       	   }
       	
       	   
       	   int left = 0;
       	   int right = N;
       	   String result = "";
       	   int count= 0;
       	   String answer = "";
       	   
       	   while(left <= right) {
       		   result ="1";
       		   count = 1;
       		   int mid = (left + right)/2;
       		   int previous = 0;
       	
       		   solve:
       		   for(int i=1; i<K; i++) {
       			   
       			   if(input[i]- input[previous]>=mid) {      				   
       				   
       				   result+="1";
       				   previous=i;
       				   count++;        				   
       				   
       				   if(count==M) {       					   
       					   break solve;
       				   }
                       
                       
       			   }else {
       				   result+="0";
       			   }
       			   
       		 }
       		   
       		   
       		   
       		   // 심판을 위치시키는 작업은 끝났으므로 나머지는 0으로 채움 
       		   while(result.length()<K) {       			   
       			   result+="0";
       			   
       		   }
       		   
       		   
               // 심판을 더 멀리 위치시킬 수 있는 경우 확인
       		   if(count==M) {       			   
       			
       			   left = mid+1;
       			   answer = result;
                   
               // 심판을 더 가까이 위치시킬 수 있는 경우 확인    
       		   }else if(count<M) {
       			   
       			   right = mid-1;
       		   }     		   
       		   
       	   }
       			   
       			   
       			System.out.println(answer);   	   
       	   
       	   
       	   
       	   }
	}

 

 

 

 

참고 블로그 : https://iheeeee6-6.tistory.com/m/117

[백준 1508] 레이스 (JAVA)