[백준] 1654 랜선 자르기 -Java

문제 - 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

 

 

문제 설명

 

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 2^31-1보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

 

예제 입력

4 11
802
743
457
539

 

예제 출력

200

---

접근 방법

 

- 문제부터 이해를 하자면 기존의 K 개의 랜선들이 있고 필요한 랜선의 개수가 N개가 필요하다 이 N개의 랜선이 가질 수 있는 최대의 길이를 구하는 문제이다

- 이문제는 이분탐색 문제이다 하지만 좀 응용해야한다 

- 어떤 점을 응용해야할까? -> 지금까지의 이분탐색 문제들을 보자면 특정 값이 들어있는 list나 배열의 특정 인덱스를 찾기 위한 문제들이 대부분이 였다 

- 하지만 여기 문제에서는 배열의 값이 아닌 랜선의 길이를 찾는 것이다

- 따라서 범위를 인덱스가 아니라 랜선의 길이로 설정해야한다

- 그러면 min 값은 랜선의 길이가 자연수라 했으니 1로 설정하고 max 값은 입력 받은 값중 최댓값으로 해서 범위를 설정한다

 

- 입력 범위는 int형의 최댓 값까지 주어진다 그래서 이 문제를 풀기위한 모든 변수들은 long 타입으로 선언해준다

 

---

코드 작성

 

코드 실패 사례

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
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());
        List<Long> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            list.add(Long.parseLong(br.readLine()));
        }

        list.sort(Comparator.comparingInt(Long::intValue));

        long min = 0;
        long max = list.get(list.size() - 1);

        while (min <= max) {
            long mid = (min + max) / 2;
            long count = 0;
            for (long value : list) {
                count += (value / mid);

            }

            if (count < M) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        System.out.println(max);
    }
}

- 위 코드는 실패 사례이다 바로 위사진과 같이 런타임 에러/ by zero가 뜨는데 이건 어떤 문제일까?

- by zero라는 에러는 나누기를 했을때 0으로 나누게 되면 에러가 발생한다

 

그럼 위 코드는 어떤 부분이 문제가 있을까?

 

- 앞서 말한 것 처럼 이 문제는 기본적인 이분 탐색 문제가 아니라 응용한 문제이다

- 대부분의 간단한 이분탐색 문제들은 범위가 0 부터 ~ 이거나 배열의 index로 푸는 문제이다 

- 이 문제는 랜선의 길이로 범위를 지정해야한다

- 위 코드 처럼 min 최솟값을 0으로 해버리게 되고 만약 max 값도 0 일때 mid = (0 + 0 ) / 2이런 문제가 발생하는거다

- 문제에서 보면 랜선의 길이는 자연수라고 했다 

- 그래서 min의 초기값을 1로 설정해둬야한다

 

 

통과 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
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());
        List<Long> list = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            list.add(Long.parseLong(br.readLine()));
        }

        list.sort(Comparator.comparingInt(Long::intValue));

        long min = 1;
        long max = list.get(list.size() - 1);

        while (min <= max) {
            long mid = (min + max) / 2;
            long count = 0;
            for (long value : list) {
                count += (value / mid);

            }

            if (count < M) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        System.out.println(max);
    }
}

 

---

풀고 느낀점

 

1. 이 문제의 핵심은 범위를 알맞게 설정하는 것 같다

2. 앞서 말한 것 처럼 0으로 나누지는 않는지 생각해 봐야한다

3. 자료형 범위를 잘 설정해줘야한다 -> 처음에 int형으로 했다가 많이 틀렸다...

4. 문제를 좀 더 자세하게 읽어 봐야겠다