백준 24508번 나도리팡 - C++(cpp) 풀이

---

 

1. 총 나도리 합을 sum이라고 하면, sum/K개의 바구니로 나도리들을 모아야 한다.
2. 총 나도리 합 sum이 K의 배수가 아니면 무조건 불가능하다.
3. 최소 횟수로 나도리를 모으려면 이미 나도리가 최대한 많이 들어있는 바구니에 모아야 한다.

 

1. 총 나도리 합을 sum이라고 하면, sum/K개의 바구니로 나도리들을 모아야 한다.

총 나도리의 수를 sum마리라고 하면, N개에 바구니에 흩어져있는 나도리들을 각 바구니에 K마리씩, 총 sum/K개의 바구니로 모으면 된다.

 

2. 총 나도리 합 sum이 K의 배수가 아니면 무조건 불가능하다.

남는 나도리 없이 전부 터트려야하므로 당연히 sum이 K의 배수가 아니면 무조건 불가능하다.

 

3. 최소 횟수로 나도리를 모으려면 이미 나도리가 최대한 많이 들어있는 바구니에 모아야 한다.

 이제 나도리들을 모을 sum/K개 바구니를 골라야 한다. 바구니에 나도리를 K마리까지 채워넣어야 하므로, 나도리 이동을 최소화하려면 이미 나도리가 최대한 많이 들어있는 바구니에 모아야 한다. 바구니들을 정렬한 뒤, 가장 나도리가 많이 들어있는 sum/K개 바구니를 선택해서  모든 바구니에 K마리의 나도리가 들어있도록 채우면 된다.

반응형

---

#include <iostream>
#include <algorithm>

using namespace std;

int N, K, T;
int nadori[100001];

int main()
{
    cin >> N >> K >> T;
    
    long long sum = 0;
    
    for(int i=0; i<N; i++) {
        cin >> nadori[i];
        sum += nadori[i];
    }
    
    if (sum % K != 0) cout << "NO";     // 총 나도리 합이 K의 배수가 아니면 불가능
    else {
        sort(nadori, nadori+N);
        
        long long cnt = 0;
        
        for(int i=0; i<sum/K; i++) {    // 가장 큰 sum/K개 바구니에 나도리를 모음
            cnt += K - nadori[N-1-i];   // K - nadori[i] = i번째 바구니를 채우기 위한 연산 횟수
        }
        
        if (cnt > T) cout << "NO";
        else cout << "YES";
    }

    return 0;
}