[BOJ/C++] 24508 - 나도리팡

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

 

---

 

나도리를 옮기는 횟수를 최소화하려면, 일단 나도리 수가 작은 바구니부터 나도리를 옮겨 비워야 합니다. (greedy)

이를 위해서는 정렬은 불가피함을 쉽게 파악할 수 있었습니다.

 

여기서 1. 투포인터를 쓰는 풀이와 2. 수학적으로 간단하게 푸는 풀이를 소개합니다. 

 

 

1. 투포인터 풀이

 

나도리가 가장 많이 들어있는 바구니부터 채워줍니다. 

나도리의 수를 기준으로 오름차순 정렬하여, 가장 앞에 있는 나도리부터 차례대로 가장 뒤에 있는 바구니에 넣습니다. 

즉, 현재까지 나도리가 가장 적게 들어있는 바구니에 있는 나도리를 나도리가 가장 많이 들어있는 바구니에 채워넣습니다. 

동시에 나도리의 이동 횟수를 기록해줍시다. 

나도리를 k개 다 채웠다면, 해당 바구니의 크기는 0으로 초기화하여 나도리가 없음을 표시합니다. 

최종적으로 모든 바구니가 비어있고, 이동횟수가 t 이하라면 YES, 그렇지 않은 경우는 NO를 출력합니다.

 

 

 

2. 수학 풀이

목표는 나도리의 수를 0으로 만드는 것입니다.

 

1) 나도리의 총 합이 k의 배수가 아닌 경우

주어진 나도리의 총 합이 k의 배수가 아니라면, 해당 케이스에서는 무슨 수를 쓰더라도 나도리의 수를 0으로 만들 수 없습니다.

따라서 이 경우에는 무조건 NO를 출력해야 합니다.

 

2) 나도리의 총 합이 k의 배수인 경우

나도리 합이 k의 배수인 경우, 이동횟수의 제한이 없다면 나도리 수를 0으로 만드는 것이 가능합니다.

따라서 이 경우에는 t번 만에 0으로 만들 수 있는지를 판별해야합니다.

 

나도리 수의 합을 sum이라고 할 때, 총 sum/k개의 바구니가 k개의 나도리로 채워져야합니다. 

이동횟수를 최소화하기 위해 나도리가 가장 많이 들어있는 바구니 sum/k개가 채워져야 하므로, 

바구니에 들어있는 나도리 수와 k의 차이만큼이 최소 이동횟수가 됩니다. 

 

이렇게 구한 최소 이동횟수를 바탕으로 답이 결정됩니다.

 

 

 

 

 

 

---

코드

투포인터 ↓

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    ll n,k,t; cin>>n>>k>>t;
    vector<ll> v(n);
    rep(i,0,n) cin>>v[i];
    sort(all(v));

    ll st = 0;
    ll en = v.size()-1;
    ll cnt = 0;

    while(v[en]<k && st<en){
        ll move = min(k-v[en],v[st]);
        cnt+=move;
        v[en] += move;
        v[st] -= move;
        while(v[st]==0 && st<en) st++;
        if(v[en]==k){
            v[en--] = 0;
        }
    }

    bool flag = (cnt>t) | *max_element(all(v));
    cout<<(flag ? "NO":"YES");
}

 

수학 ↓

#include<bits/stdc++.h>
using namespace std;
#define X first
#define Y second
#define rep(i,x,y) for(ll i=x;i<y;i++)
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tiii;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
/*----------------------*/

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    ll n,k,t; cin>>n>>k>>t;
    vector<ll> v(n);
    ll sum = 0;
    rep(i,0,n){
        cin>>v[i];
        sum+=v[i];
    }

    ll cnt = 0;
    sort(rall(v));
    rep(i,0,sum/k) cnt+=k-v[i];

    bool flag = (sum%k) | (cnt>t);
    cout<<(flag?"NO":"YES");

}