[ C++/cpp ] 백준 (1654 랜선 자르기) ⭐이분 탐색 💦

백준 1654번 문제이름

(실버 2)

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

 

 

(정답 코드)

#include <iostream>
#include <vector>

using namespace std;

int cnt(int x, const vector<int>& num) {
    
    long ans = 0;
    
    for(int i=0; i<num.size(); i++) {
        ans += num[i]/x;
    }
    return ans;
}


int solution(const vector<int>& num, int n, long sum) {
    
    long left = 1;
    long right = sum/n; // 토막 가능한 최대 길이
    long mid;
    while(left<=right) {
        
        mid = (left+right)/2;
        
        if( cnt(mid, num) >=n ) {
            left = mid+1;
        } else {
            right = mid-1;
        }
    }
    
    return right;
}

int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 
    
    int k, n, temp;
    long sum=0;
    cin >> k >> n;
    vector<int> num;
    
    while(k--) {
        cin >> temp;
        sum += temp;
        num.push_back(temp);
    }
    
    // 연산 및 출력
    cout << solution(num, n, sum);
    
    return 0;
}

 

 

📖 풀이

 

1. 도입 - 이분탐색 떠올리기 !

https://somde.tistory.com/129

[ 이분탐색🚩] 개념 + 활용 문제 ( 백준 c++ 1920 수 찾기 / 10816 숫자 카드 2 ) #UpperBound #LowerBound

 예전 이분 탐색 포스트를 보면, 최댓값과 최소값 키워드를 보면 이분 탐색을 의심해보라는 조언이 있었습니다. 커팅 가능한 가장 긴 길이까지의 전체 범위를 이분 탐색하며 n개 이상의 토막내는 것이 가능한 랜선 길이의 최댓값을 찾아나가는 것이 이 문제의 핵심입니다.

 

2. 풀이 - upperbound 방식

 전체 랜선의 수를 더해 n 으로 평균내면, 가능한 가장 긴 랜선 토막의 길이가 됩니다. 이 값을 right, 1을 left로 설정하고 이분탐색을 실시합니다.

이분 탐색만 떠올렸면 문제를 쉽게 풀 수 있지만, 조금 주의해야 할 점은 " N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. " 즉, n토막 이상 내도 괜찮다는 점입니다. 키값에 해당하는 순간 탐색에 성공해 종료하는 기초적인 이분 탐색 문제와는 조금 다른 부분입니다. upperbound 방식을 활용해야합니다. 주어진 값보다 큰 key 중 가장 작은 인덱스를 찾아야한다는 사실에 집중하며  오른쪽 - 왼쪽으로 이동하는 경우를 잘 설정해야 합니다 !

 

+ 함수 모듈화

알튜비튜 이후로 습관이 된.. 함수 쪼개기 ! 

저는 2개의 함수로 문제를 쪼개 풀이했습니다.

1. cnt 함수:
   • 주어진 길이 x로 각 케이블을 잘랐을 때 만들어질 수 있는 케이블의 총 개수를 계산하는 함수
2. solution 함수:
   • 이분 탐색을 통해 최대 길이를 찾는 함수
     right를 반환해야 합니다 ! 예제 몇 개 시뮬 돌려보면 쉽게 구현할 수 있을 것입니다.
     
   • right의 초기값:
     right의 초기값을 sum / n으로 설정한 것은 최대로 가능한 랜선의 크기는 전체 랜선 길이를 n토막으로 나눈 값보다 작을 것이기 때문입니다 ㅎㅎ

꼬질꼬질한 글씨로 예제 쓰면서 시뮬 돌려봄 :)

---

 

💥 트러블 슈팅

자료형 주의보 !

 이분탐색으로 문제를 풀어 제출했더니 2%나 47%에서 틀렸다는 결과를 받았습니다. 풀이의 큰 흐름은 맞는 것 같았는데, 특정 코너 케이스에서 틀린 것 같아 먼저 다양한 예제를 떠올려보며 직접 시뮬레이션을 해보았습니다. n이 1인 경우, k가 1경우 이런 극단의 케이스도 검토해보고, 직접 예제를 만들고 검증도 해보았습니다. 그러나.. 여러 번 확인해도 틀릴 만한 부분이 보이지 않았습니다 !

 

 한참을 씨름하다가 덮어두고.. 잠시 후 맑은 정신으로 다시 보니, 바로 원인을 발견했는데, 자료형 때문에 오버플로우가 발생한 것 같았습니다.

 

 "K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다."

 따라서 int형에 담기에는 sum, right 등의 변수 범위가 넘칠 가능성이 있었습니다. int 대신 넉넉한 자료형인 long을 사용하니 바로 정답이 나왔습니다. 자료형만 바꾸면 되는 문제를 몇 번이나 헤매다니... 미처 생각지 못한 기초적인 부분에서의 실수.. 등잔 밑이 어두운 기분입니다. 꼬일 땐 조급하게 굴지말고, 문제 조건부터 다시 꼼꼼히 읽어보여 차근차근 다시 가 보아야함을 깨닫습니다.