6236 용돈관리 (미완)

이렇게 생각했고

 

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

bool check(i64 mid, int k, vector<int> v){
    i64 c = 0;
    i64 m = mid;
    for(int i = 0; i < v.size(); i++){
        if(m-v[i] < 0){
            m = mid;
            c++;
        }
        m -= v[i];
    }
    if(c <= k)
        return true;
    return false;
}

int main() {
    int n, m, sum = 0;
    scanf("%d %d", &n, &m);
    vector<int> v(m);
    
    for(int i = 0; i < m; i++){
        scanf("%d", &v[i]);
        sum += v[i];
    }
    
    int low = 0;
    int high = sum;
    
    while(true){
        if(low+1 == high)
            break;
        
        i64 mid = (low + high)/2;
        
        if(check(mid, m, v))
            high = mid;
        else 
            low = mid;
    }
    printf("%d", high);
    
    return 0;
}

이렇게 짰다. 예제를 돌려보니 1이 나왔다. 나머지는 내일 생각해봐야겠다.

아 알고보니 v(n)을 해야하는데 크기를 m으로 잡았다. 비슷한 문제 많이 풀어 좀 헷갈렸다. 근데 이거 고쳐도 답이 다르게 나온다. 좀 더 고민해봐야겠다. 

 

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

bool check(i64 mid, int k, vector<int> v){
    i64 c = 0;
    i64 m = mid;
    for(int i = 0; i < v.size(); i++){
        if(m-v[i] < 0){
            m = mid;
            c++;
        }
        m -= v[i];
    }
    if(c < k)
        return true;
    return false;
}

int main() {
    int n, m;
    i64 sum = 0;
    scanf("%d %d", &n, &m);
    vector<int> v(n);
    
    for(int i = 0; i < n; i++){
        scanf("%d", &v[i]);
        sum += v[i];
    }
    
    int low = 0;
    i64 high = sum;
    
    while(true){
        if(low+1 == high)
            break;
        
        i64 mid = (low + high)/2;
        
        if(check(mid, m, v))
            high = mid;
        else 
            low = mid;
    }
    printf("%lld", high);
    
    return 0;
}

 

뭔가 if(c <= k) 이 부분에 답이 있을 것 같아서 이걸  if(c < k) 이렇게 고쳤다. 그랬더니 예제 답과 맞게 나온다. 근데 틀렸다 역시 생각을 하고 짜야겠다. 

 

음 생각해도 모르겠다