[백준] 1654번: 랜선 자르기 (C++)

 

이분 탐색을 사용하는 문제로, 기존의 나무 자르기 문제와 비슷한 유형이다

최대 길이를 가진 랜선을 구한 후, 최대 길이의 랜선의 길이에서 이진 탐색을 수행한다

랜선들을 자른 몫을 합 한 후, 몫이 입력 값 이상이 나타나는 최대 길이를 구할 수 있다.

 

처음에는 최대 길이를 구하기 때문에 long long cut 변수를 사용하지 않고 바로 int mid를 출력했지만 오류가 나타났다

아래 사이트에서 별도로 새로운 변수를 사용하여 출력하는 것을 참고하였다

 

[C/C++] 백준 1654번 - 랜선 자르기 :: 코딩 공부 일지 (tistory.com)

[C/C++] 백준 1654번 - 랜선 자르기

 

메모리 초과가 뜨지 않는 이상 변수를 최대한 할당하여 사용하는 것이 좋은 것 같다

 

 

// baekjoon 1654

#include<iostream>
#include<algorithm>
#include<cmath>

using namespace std;

// codes for fast I/O
void init(){
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);
}


int main(){
    init();
    
    int n;
    cin >> n;
    
    int k;
    cin >> k;
    
    int longest = 0;
    
    int arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        if(longest < arr[i]){
            longest = arr[i];
        }
    }
    
    long long left = 1;
    long long right = longest;
    long long mid = (left + right) / 2;
    long long sum = 0;
    
    long long cut = 0;
    
    
    while (left <= right) {
        sum = 0;
        mid = (left + right) / 2;
        
        for(int i = 0; i < n; i++){
            sum += arr[i] / mid;
        }
        if (sum >= k){
            left = mid + 1;
            
            if (cut < mid){
                cut = mid;
            }
            
        }
        else {
            right = mid - 1;
        }
        
        
    }
    
    cout << cut;
    
    
}

코딩을 처음 배울 때 변수를 적게 쓰려는 습관을 가져서 그런가 변수를 계속 선언하는 것이 아직 익숙하진 않다

그래도 반복문에 관여하는 변수는 직접 건드리지 않고 새로운 변수를 선언하여 작업하는 것이 좋은 접근인 것 같다