[백준] no.1654: 랜선 자르기

문제

: 길이가 서로다른 K개의 랜선을 잘라서, N개의 랜선을 만들것임

: N개의 랜선을 최대한 길게 자르는 것이 목표임 (즉, 1개의 랜선길이를 가장 길게 N개 뽑는것)

 

문제 링크 : https://www.acmicpc.net/problem/1654

---

원리

1) 브루트 포스

2) 이진탐색

---

나의 코드

1) 브루트 포스 : 너무 오래걸린다

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 K = Integer.parseInt(st.nextToken());  // 이미 가진 랜선수   1<= K <= 10000
        int N = Integer.parseInt(st.nextToken());  // 필요한 랜선수      1<= K <= 1000000   // 항상 K <= N
        int[] arr = new int[K];
        int total = 0;
        for(int i = 0; i < K; i++) {
            int temp = Integer.parseInt(br.readLine());
            arr[i] = temp;
            total += temp;
        }
        int cm = total/N;
        int num = 0;
        while(num!=N) {
            num=0;
            for(int i = 0; i <arr.length; i++) {
                num += arr[i]/cm;
            }
            cm--;
        }

        System.out.println(cm+1);
    }
}

 

2) 이진탐색 : 이진탐색으로 푸는게 옳지만, 내 코드의 조건문은 여러 문제가 있다

문제점1. 특정 값에서 탈출을 못함 : 예를들어 3 10, 10,10,10 이면, 2으로 나누자니 15개고, 3으로 나누자니 9개

문제점2. while문 탈출 후 result미반영 : while문 탈출 후 조건에 따라 바로 값이 출력되버림

예를들어 4 200, 200, 200, 200, 200 일 경우, 직전 result인 199로 바로 출력됨

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

public class no1654 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[K];
        long total = 0;
        for(int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            total += arr[i];
        }
        long up = total/N;
        long down = 0;
        long mid;
        long result = 0;

        while(true) {
            mid = (up + down)/2;
            int count = 0;

            for(int i = 0; i <K; i++) count += arr[i]/mid;

            if(count < N) up = mid;
            else if (count > N) down = mid;
            else {
                if(mid>result) {
                    result = mid;
                    down = mid;
                }
                else break;
            }
        }
        System.out.println(result);
    }
}

 

---

레퍼런스 코드

public class no1654 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int K = Integer.parseInt(st.nextToken());
        int N = Integer.parseInt(st.nextToken());
        int[] arr = new int[K];
        long max = 0;
        for (int i = 0; i < K; i++) {
            arr[i] = Integer.parseInt(br.readLine());
            if(max < arr[i]) max = arr[i];
        }
        max++;
        long min = 0;
        long mid;
        while (min < max) {
            mid = (max + min) / 2;
            long count = 0;
            for (int i = 0; i < arr.length; i++) count += (arr[i] / mid);
            if(count < N) max = mid;
            else min = mid + 1;
        }
        System.out.println(min - 1);
    }
}

참고 링크 : https://st-lab.tistory.com/269