BOJ 1654번 랜선 자르기

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

GitHub : https://github.com/junho0956/Algorithm/blob/master/1654/1654/%EC%86%8C%EC%8A%A4.cpp

 

아 다시는 풀고싶지 않은 문제이다.

12번의 제출 끝에 정답을 맞춘 문제다.

막힐 때는 고집부리지 않고 게시판도 읽어보고 검색도 해보고 배우는 습관을 들여야겠다.

 

12번의 제출 끝에 알게된 결함은 int <-> long long 때문이였다.

타입 변환을 제외하고는 크게 문제될게 없는 문제이다.

 

#include <iostream>
#include <vector>
#include <limits.h>
using namespace std;
 
vector<long long> v;
long long N, K, k_num, Max;
 
long long solve() {
    long long left = 0, right = INT_MAX;
    long long result = 0;
 
    while (left <= right) {
        long long mid = (left + right) / 2;
        long long cnt = 0;
        for (long long i = 0; i < v.size(); i++) cnt += v[i] / mid;
 
        if (cnt >= N) {
            left = mid + 1;
            result = result < mid ? mid : result;
        }
        else right = mid - 1;
    }
 
    return result;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    cin >> K >> N;
    for (long long i = 0; i < K; i++) {
        cin >> k_num;
        v.push_back(k_num);
        Max = Max < k_num ? k_num : Max;
    }
 
    long long result = solve();
    cout << result;
 
    return 0;
}