[이진탐색][Java][BOJ] #1654. 랜선 자르기

#이진탐색  #Silver2

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

🌷 문제 설명

✏️ 백준 연습문제: #1654. 랜선 자르기
집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

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

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

입출력 예

예제 입력	예제 출력
4 11 802 743 457 539	200

 

💡 해결 포인트

1. 이진탐색
- n이라는 정수가 있으면, 최솟값 1, 최댓값 n으로 배열처럼 생각해서 탐색할 수 있다!

2. int와 long
- int의 범위: -2,147,483,648 ~ 2,147,483,647
- long의 범위: -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807
- 범위 제한에  "랜선의 길이는 2^31-1보다 작거나 같은 자연수" 라는 말이 있는데, 이는 2,147,483,647임.
- 따라서 overflow가 발생할 가능성이 있으므로 int가 아닌 long으로 선언 필요

3. forEach문
- 자바에서 forEach는 for (타입 변수명: 배열) 형태로 구현할 수 있다
- num은 변수, numbers는 배열

 

🌷 내 코드

1. 이진탐색

어레이랑 리스트어레이랑 리스트의 차이점을 모르지만 이진탐색 했다!ㅋㅋㅋ 그런데 처음엔 진짜 그냥 while문에 for문까지 총동원한 무지성 코딩을 했다가 시간초과 나서 힌트를 보니 이진탐색.. 아니 배열이 정렬돼서 들어오는게 아닌데 왜 이진탐색을 써야하는지 약간 뇌정지가 왔지만 일단 결론에 방법을 끼워넣어보기로 했다. 

이진탐색에 대해 잘 모르겠단 사람이 있다면 과거의 나자신이 여기 아주 잘 정리해 놨다! 나도 다시 봤는데 다시 봐도 잘 정리한듯.. 근데 코드가 자바스크립트인건 감안하고 봐야 함

[Algorithm I][JavaScript] 이진탐색(Binary Search)

 

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

public class BOJ_1654 {
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("example.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 첫 번째 줄 입력
        String[] firstLine = br.readLine().split(" ");
        int K = Integer.parseInt(firstLine[0]); // 랜선 개수
        int N = Integer.parseInt(firstLine[1]); // 필요한 랜선 개수

        // K개 랜선 길이 입력
        long[] numbers = new long[K];
        for (int i = 0; i < K; i++) {
            numbers[i] = Long.parseLong(br.readLine());
        }

        // 최대값 찾기
        long max = numbers[0];
        for (int i = 1; i < K; i++) {
            if (numbers[i] > max) {
                max = numbers[i];
            }
        }

        // 이진탐색 
        long left = 1; // 최소 길이
        long right = max; // 최대 길이
        long answer = 0;

        while (left <= right) {
            long mid = (left + right) / 2;
            long sum = 0;

            // mid 길이로 만들 수 있는 랜선 개수 계산
            for (long num : numbers) {
                sum += num / mid;
            }

            // 조건에 따라 범위 조정
            if (sum >= N) {
                answer = mid; // 가능한 길이 저장
                left = mid + 1; // 더 긴 길이 탐색
            } else {
                right = mid - 1; // 더 짧은 길이 탐색
            }
        }

        // 결과 출력
        System.out.println(answer);
    }
}

 

🌷 코멘트

범위 고려하는 버릇이 잘 안들어 있어서 int long 때문에 멘붕이었다.. 백준은 테케좀 몇개 더 줬으면 좋곘다ㅠ

 

 

---

블로그 내용에 문제가 있다면 댓글 혹은 아래로 연락주세요!

~대가리 꽃밭인 디지털 노마드가 꿈이예요~

🧚‍♀️ Gyumin Lee

📧 gyumin.q.lee@gmail.com

qminlee723 - Overview