링크 → https://www.acmicpc.net/problem/2110

• 아영

  • 코드

  package Baekjoon.java.gold;
  
  import java.io.BufferedReader;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  public class boj2110 {
      public static void main(String[] args) throws Exception{
          BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
          StringTokenizer st = new StringTokenizer(br.readLine());
  
          int N = Integer.parseInt(st.nextToken());
          int C = Integer.parseInt(st.nextToken());
  
          int[] houses = new int[N];
          for (int i = 0; i < N; i++) {
              houses[i] = Integer.parseInt(br.readLine());
          }
          Arrays.sort(houses);
          int prev = houses[0];
          int min = Integer.MAX_VALUE;
          for (int i = 1; i < N; i++) {
              int gap = houses[i]-prev;
              min = Math.min(min,gap);
              prev = houses[i];
          }
  
          int answer = 0;
          int max = houses[N-1]-houses[0];
  
          if(C==2){
              answer = max;
          }else {
              int left = min;
              int right = max;
              while(left<=right){
                  int mid = (left+right)/2;
                  prev = houses[0];
                  int cnt = 1;
                  for (int j = 1; j < N; j++) {
                      int distance = houses[j]-prev;
                      if(cnt==C) break;
                      if(distance>=mid){
                          prev = houses[j];
                          cnt+=1;
                      }
                  }
                  if(cnt>=C){
                      left = mid+1;
                      answer = mid;
                  }else{
                      right = mid-1;
                  }
  
              }
          }
          System.out.println(answer);
  
      }
  }
  

  • 시간,메모리

  

• 은영

  • 코드
  • 시간,메모리

• 건

  • 코드

  package day_0424;
  
  import java.io.BufferedReader;
  import java.io.IOException;
  import java.io.InputStreamReader;
  import java.util.Arrays;
  import java.util.StringTokenizer;
  
  public class BOJ2110 {
  
  	public static void main(String[] args) throws IOException{
  		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  		StringTokenizer stk = new StringTokenizer(br.readLine());
  		
  		int n = Integer.parseInt(stk.nextToken());
  		int c = Integer.parseInt(stk.nextToken());
  		
  		int[] house = new int[n];
  		
  		for (int i = 0; i < n; i++) {
  			house[i] = Integer.parseInt(br.readLine());
  		}
  		
  		Arrays.sort(house);
  		
  		long start = 1, end = house[n-1] - house[0], mid = 0;
  		int nowIdx = 0, sum = 1;
  		while (start <= end) {
  			nowIdx = 0;
  			mid = (start + end) / 2;
  			sum = 1;
  			for (int i = 1; i < n; i++) {
  				if (house[i] - house[nowIdx] >= mid) {
  					nowIdx = i;
  					sum += 1;
  				}
  			}
  			
  			if (sum < c) {
  				end = mid - 1;
  			} else {
  				start = mid + 1;
  			}
  		}
  		
  		System.out.println(end);
  	}
  
  }
  

  • 시간,메모리

  

• 용문

  • 코드

  class BJ2110 {
      
      private var N: Int = 0
      private var C: Int = 0
      private var houses: [Int] = []
      private var answer: Int = 0
      
      func solve() {
          readComponents()
          calc()
          writeAnswer()
      }
      
      private func readComponents() {
          let temp = readLine()!.split(separator: " ").map { Int($0)! }
          self.N = temp[0]
          self.C = temp[1]
          
          for _ in 0..<N {
              houses.append( Int(readLine()!)! )
          }
      }
      
      private func calc() {
          houses.sort()
          
          var low = 1
          var high = houses.last! - houses.first! + 1
          
          while low < high {
              let mid = (low + high) / 2
              var count = 1
              
              var last = houses[0]
              
              for index in 1..<houses.count {
                  if houses[index] - last >= mid {
                      count += 1
                      last = houses[index]
                  }
              }
              
              if count < C {
                  high = mid
              } else {
                  low = mid + 1
              }
          }
          
          answer = low - 1
      }
      
      private func writeAnswer() {
          print(answer)
      }
  }
  
  BJ2110().solve()
  

  • 시간,메모리