1654 랜선 자르기

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

어떻게 풀지 감은 왔다. 랜선의 최댓값을 구하는 거니깐 나무 자르는 문제처럼 범위를 정해서 그 범위 중 최댓값을 구하면 되지 않을까 싶었음. [ ㄱ, ㄴ] 여기서 ㄱ이 만족하는 값 중 최댓값이 된다. 

 

또 만족하는지 안 하는지도 구하는 법을 알겠다. 802같은 경우 200으로 나누면 4가 되므로, 만족하는지 알고 싶으면 그냥 몫을 구하면 된다. 몫들의 합이 랜선의 개수가 된다. 

 

하지만 결과는 런타임 에러... 것도 세 번이나.. 아마 / mid로 하면서 mid가 0이 돼서 그렇지 않을까 싶었는데 이걸 어떻게 해야할지 모르겠다. 일단 mid가 0이 될 수 있는가? 이게 첫 문제고 두번째는 mid가 0이라면 처리는 어떻게 하나? 이 두가지를 몰라서 해결 못하겠다.. 

 

그리고 내가 범위를 잘 지정했는지 모르겠다. 만족하는 최솟값은 1로 잡고 만족하지 않는 최댓값은 길이 중 최댓값으로 설정했다. 그런데 1 1 10을 넣으면 9가 나온다ㅋㅋ 10이 나와야 하는데.//. 아무튼 최솟값은 맞는 것 같은데 최댓값이 어떻게 되는지 모르겠다. 어렵다.. 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool cut(int mid, int n, vector<int> v){
    i64 sum = 0;
    
    for(int i = 0; i < v.size(); i++)
        sum += v[i] / mid;
    if(sum >= n)
        return true;
    else
        return false;
}

int main() {
    int k, n;
    scanf("%d %d", &k, &n);
    vector<int> v(k);
    
    for(int i = 0; i < k; i++)
        scanf("%d", &v[i]);
        
    int low = 1;
    int high = *max_element(v.begin(), v.end()) + 1;
        
    while (true){
        if(low == high -1)
            break;
        int mid = (low+high)/2;
        if(cut(mid, n, v))
            low = mid;
        else
            high = mid;
    }
    
    printf("%d", low);
        
    return 0;
}

 

---

예상외로 문제는 오버플로우였다

 

int mid = (low+high)/2; 여기서 문제 없다고 생각했는데 low + high 부분에서 오버플로우가 발생한다.. 생각도 못한 부분이네..

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool cut(i64 mid, int n, vector<int> v){
    int sum = 0;
    
    for(int i = 0; i < v.size(); i++)
        sum += v[i] / mid;
    if(sum >= n)
        return true;
    else
        return false;
}

int main() {
    int k, n;
    scanf("%d %d", &k, &n);
    vector<int> v(k);
    
    for(int i = 0; i < k; i++)
        scanf("%d", &v[i]);
        
    i64 low = 1;
    int high = *max_element(v.begin(), v.end());
        
    while (true){
        if(low == high-1)
            break;
        i64 mid = (low+high)/2;
        if(cut(mid, n, v))
            low = mid;
        else
            high = mid;
    }
    
    printf("%lld", low);
        
    return 0;
}

그래서 터질만한 부분을 바꿔줬고... 하지만 범위 지정 잘못해서 틀렸고..

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool cut(i64 mid, int n, vector<int> v){
    int sum = 0;
    
    for(int i = 0; i < v.size(); i++)
        sum += v[i] / mid;
    if(sum >= n)
        return true;
    else
        return false;
}

int main() {
    int k, n;
    scanf("%d %d", &k, &n);
    vector<int> v(k);
    
    for(int i = 0; i < k; i++)
        scanf("%d", &v[i]);
        
    i64 low = 1;
    int high = *max_element(v.begin(), v.end()) + 1;
        
    while (true){
        if(low == high-1)
            break;
        i64 mid = (low+high)/2;
        if(cut(mid, n, v))
            low = mid;
        else
            high = mid;
    }
    
    printf("%lld", low);
        
    return 0;
}

다시 범위 바꿔줬다. 

ㅋㅋㅎㅎㅋㅋ 이번에는 시간초과로 틀렸다. 컴파일 에러랑 메모리 초과만 모우면 모든 에러를 다 만날 수 있다. 야호

 

---

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using i64 = long long;

bool cut(i64 mid, int n, vector<i64> v){
    i64 sum = 0;
    
    for(int i = 0; i < v.size(); i++)
        sum += v[i] / mid;
    if(sum >= n)
        return true;
    else
        return false;
}

int main() {
    int k, n;
    scanf("%d %d", &k, &n);
    vector<i64> v(k);
    
    for(int i = 0; i < k; i++)
        scanf("%lld", &v[i]);
        
    i64 low = 1;
    i64 high = *max_element(v.begin(), v.end()) + 1;
        
    while (true){
        if(low == high -1)
            break;
        i64 mid = (low+high)/2;
        if(cut(mid, n, v))
            low = mid;
        else
            high = mid;
    }
    
    printf("%lld", low);
        
    return 0;
}

눈물이 난다 드디어 맞았다. 오만군데 다 터져가지고는ㅜㅜㅜ 앞으로 입력이 2^31 -1처럼 터지게 생겼으면 그냥 바로 i64쓰는게 좋을 것 같다.