랜선자르기(1654)

게시 2023/12/11

By Kim Jung Wook 10 분읽는 시간

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

public class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();

    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int k = Integer.parseInt(st.nextToken());
    int n = Integer.parseInt(st.nextToken());
    
    int[] arr = new int[k];

    int sum = 0;
    for(int i = 0; i < k; i++){
      int a = Integer.parseInt(br.readLine());
      arr[i] = a;
      sum += a;
    }
    
    int size = sum / n;
    int cnt = 0;
    
    while(true){
      if(cnt == n) break;
      else{
        cnt = 0;  
        size--;
      } 
      
      for(int i = 0; i < k; i++){
        cnt += arr[i] / size;
      }
    }
    
    bw.write(size + "");
    bw.flush();
    bw.close();
    br.close();
  }
}

시간초과 발생
size를 1씩 줄이다보니 랜선의 길이가 길거나 랜선의 필요 갯수가 작을 때 기준점이 되는 size가 너무 크게 
나올 경우 for문이 돌아가는 시간이 많이 걸린다고 판단하였음.

시간초과로 인해서 for문이 돌아가는 횟수를 줄이고자 하였음

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

public class Main{
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();

    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int k = Integer.parseInt(st.nextToken());
    int n = Integer.parseInt(st.nextToken());
    
    double[] arr = new double[k]; // 입력값(길이)

    // 초기 나누는 길이 구하기
    double sum = 0.0;
    for(int i = 0; i < k; i++){
      double a = Double.parseDouble(br.readLine());
      arr[i] = a;
      sum += a;
    }
    
    int size = (int)(sum / n); // 모든 랜선의 합에서 필요갯수로 나눠 기준점 잡기
    
    bw.write(size(arr, n, size) + "");
    bw.flush();
    bw.close();
    br.close();
  }
    
  public static int size(double[] arr, int n, int m){
    int size = m;
    double[] dArr = new double[arr.length];
    int cnt = 0;
    int top = 0;
    int index = 0;

    for(int i = 0; i < arr.length; i++){
      dArr[i] = Math.floor((arr[i] / size) * 10) / 10.0; // 각 랜선을 기준점으로 나눠 갯수구하기
      cnt += (int)Math.floor(dArr[i]); // 갯수이기 때문에 정수형으로 바꿔서 합구하기
    }
        
    if(cnt == n) return size;
    else {
      for(int i = 0; i < dArr.length; i++){
        if((int)Math.floor(dArr[i] * 10) % 10 > top){
          top = (int)Math.floor(dArr[i] * 10) % 10;
          index = i;
        }
      }
      // 몫 중에서 소수점이 제일 정수와 가까운 애를 구하기
      
      size = (int)(arr[index] / Math.ceil(dArr[index])); // 크기를 다시 설정
      
      return size(arr, n, size); // size메소드 다시 호출
    }
  } 
}

메모리 초과 발생
1. 기준점이 되는 크기를 구하고 1차로 나누어 본다
2. 몫을 더하여 n과 비교하기
3. 조건을 충족 못시키면
4. 몫을 double형으로 하여 소수 첫째자리의 값 중 크기가 큰 애의 몫(나오는 개수)를 +1하여 다시 나눠보고 나오는
몫(길이)를 바탕으로 나머지 것들도 잘라서 나오는 몫(개수)를 더하여 n과 비교하기

이분탐색을 이용하여 문제풀이

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

public class Main{
  public static void main(String[] args) throws IOException {
      
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int k = Integer.parseInt(st.nextToken());
    int n = Integer.parseInt(st.nextToken());
    
    int[] arr = new int[k];
    
    for(int i = 0; i < k; i++){
      arr[i] = Integer.parseInt(br.readLine());
    }
    
    int cnt = result(arr, n);
    
    bw.write(arr[0]/cnt + "");
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static int result(int[] arr, int n){
    int lo = 0;
    int hi = n;
    
    while(lo < hi){
      int mid = (lo + hi) / 2;
      
      int cm = arr[0] / mid;
      
      int sum = 0;
      
      for(int i = 0; i < arr.length; i++){
        sum += arr[i] / cm;
      }
      
      if(n <= sum){
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    
    return lo;
  }
}

길이와 필요 갯수 중 어느 것을 범위로 잡을 것인가에 대해서, 필요 갯수의 조건이 더 작았기에 필요갯수를 이분탐색 하기로
결정하였고, mid의 갯수를 기준으로 가장 길이가 긴 랜선을 나눈 몫(길이)로 다른 랜선을 나눠 몫을 합산(잘라진 갯수)하여 
필요 갯수와 비교하는 방식으로 진행하였다

틀렸습니다. 발생함
만약 2개의 랜선이 있고, 2개가 필요, 각각의 랜선의 길이는 1이라고 하였을 때,
Exception in thread "main" java.lang.ArithmeticException: / by zero 발생. 즉 0으로 나눠지는 경우가 생김

갯수말고 길이를 이분탐색하기로 변경.
문제에서 
'기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자.'
라는 문구가 있었기에 lo를 0이 아닌 1로 설정

그리고 길이의 최대값을 구하는 것이기 때문에 이분탐색에서 하위경계가 아닌 상위경계를 구하도록 이분탐색 코드 변경

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

public class Main{
  public static void main(String[] args) throws IOException {
      
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    
    StringTokenizer st = new StringTokenizer(br.readLine());
    
    int k = Integer.parseInt(st.nextToken());
    int n = Integer.parseInt(st.nextToken());
    
    long[] arr = new long[k];
    
    long max = 0;
    
    for(int i = 0; i < k; i++){
      arr[i] = Integer.parseInt(br.readLine());
      max = (max < arr[i])? arr[i] : max;
    }
    
    long result = result(arr, n, max);
    
    bw.write(result + "");
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static long result(long[] arr, int n, long max){
    long lo = 1;
    long hi = max;
    
    while(lo < hi){
      long mid = (lo + hi) / 2;
      
      int sum = 0;
      
      for(int i = 0; i < arr.length; i++){
        sum += arr[i] / mid;
      }
      
      if(sum < n){
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    
    return lo - 1;
  }
}

틀렸습니다. 발생
위의 경우에도 
2 2
1
1
입력 시, 반환값이 0으로 반환되는 경우가 발생하였다. (올바른 답은 1)

범위를 작은값을 1로 시작하지 말고, 최대값에 +1을 하여, 최대값도 선택이 가능하도록 변경

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

public class Main{
    public static void main(String[] args) throws IOException {
        
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
      
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      int k = Integer.parseInt(st.nextToken());
      int n = Integer.parseInt(st.nextToken());
      
      long[] arr = new long[k];
      
      long max = 0;
      
      for(int i = 0; i < k; i++){
        arr[i] = Integer.parseInt(br.readLine());
        max = (max < arr[i])? arr[i] : max;
      }
      
      long result = result(arr, n, max);
      
      bw.write(result + "");
      bw.flush();
      bw.close();
      br.close();
  }
  
  public static long result(long[] arr, int n, long max){
    long lo = 0;
    long hi = max + 1;
    
    while(lo < hi){
      long mid = (lo + hi) / 2;
      
      int sum = 0;
      
      for(int i = 0; i < arr.length; i++){
        sum += arr[i] / mid;
      }
      
      if(sum < n){
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    
    return lo - 1;
  }
}

성공
메모리 : 17352 KB
시간 : 172 ms

알고리즘, 문제

알고리즘문제

시간초과로 인해서 for문이 돌아가는 횟수를 줄이고자 하였음

이분탐색을 이용하여 문제풀이

인기 태그