[백준] 24502 - blobsad (c++)

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

 

문제 요약

N개의 통을 나란히 있고 각 통에 있는 블롭 개수가 주어진다. 한 블롭을 인접한 칸으로 옮기는데 1초가 걸린다.

모든 통의 블롭 개수를 K의 배수로 만드는데 걸리는 최소 시간을 구해라.

 

풀이 (N)

• 그리디

전체 블롭의 수가 K의 배수라면 i~j까지 구간의 블롭개수를 모두 K의 배수로 맞췄을 때 j+1~N의 블롭 수의 합이 K배수가 된다. 따라서 모든 i를 순회하며 {i,i+1} 쌍에서 어느 쪽으로 몇 마리 옮길지만 그리디하게 결정해줘도 된다. 

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define mid (st+en>>1)

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n,k;cin>>n>>k;
    vector<ll> o(n);
    for(auto&x:o)cin>>x;
    
    ll ans=0;
    for(int i=0;i<n-1;i++) {
        if(o[i]%k*2<k)
            o[i+1]+=o[i]%k,ans+=o[i]%k;
        else
            o[i+1]+=o[i]%k,ans+=k-o[i]%k;
    }

    if(o[n-1]%k)
        cout<<"blobsad";
    else    
        cout<<ans;
}