BOJ 7775 : 최종 순위

• 문제 링크 : boj.kr/7775
• 난이도 : G3
• 태그 : 해 구성하기

7775번: 최종 순위

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n, p, k, d;
    cin >> n >> p >> k >> d;
    
    vector<int> arr(n);
    if(d == 1) {
        for(int i = 0; i < k; i++) {
            arr[i] = p / k;
        }
        p -= arr[0] * k;
        if(n == k && p != 0) {
            cout << "Wrong information";
            return 0;
        }
        for(int i = k; i < n; i++) {
            arr[i] = min(arr[0] - 1, p);
            p -= arr[i];
            if(p == 0) break;
        }
        if(p > 0) {
            cout << "Wrong information";
            return 0;
        }
    }
    else {
        for(int i = 0; d > 0; i++) {
            arr[i] = d-1;
            p -= arr[i];
            d--;
        }
        if(p < 0) {
            cout << "Wrong information";
            return 0;
        }
        arr[0] += p;
    }
    
    for(auto u : arr) cout << u << "\n";

    return 0;
}

---

풀이

d가 1이 아닌 경우부터 생각해보자.

서로 다른 점수의 수가 d개이면서 점수의 합이 최소가 되는 경우는 어떤 경우일까?

상위권 d명의 점수가 $d-1, d-2, \cdots , 1, 0$이면 된다.

만약 p가 이 점수들의 합보다 작다면 불가능한 경우이다.

p가 이 점수들의 합보다 크다면 남는 점수를 가장 높은 점수에 몰아주면 된다.

당연히 상위권 d명을 제외한 나머지의 점수는 0점이다.

 

d가 1인 경우에는 다른 방식으로 접근해야 한다.

주어진 p를 k명에게 최대한 나눠줘보자. 나눠주고 나서 나머지가 생기거나 생기지 않을 것이다.

나머지가 생기지 않았다면 이미 조건을 만족했으니 문제가 없다.

문제는 나머지가 발생한 경우이다.

나머지를 k등까지에게는 줄 수 없으니 k+1등부터 나눠주어야한다.

이때게각각의 점수가 k등까지의 점수를 넘지 않게 나눠준다.

나머지를 전부 나눠줄 수 없다면 불가능한 경우이다.