백준 7775, 최종 순위

개요

문제 링크
골드 3, Greedy
n개의 수를 합이 p이고 상위 k개까지 서로 다른 수의 개수가 d가 되도록 비오름차순 출력하기

---

접근

1. 밤에 잠이 안와서 풀었던 문제. 풀고나니 단순했지만 시행착오가 많았다. 우선 핵심은 d에 의해 결정된다.

2. 만약 d가 2이다. 그러면 {p,0,0...} 으로 1등에 몰빵해주면 된다. 예시에서는 그렇게 하지 않아서 틀리는 경우가 많았다.

3. 그렇다면 d가 3이면? {p-1,1,0..} 으로 2등에 1을 주고 나머지는 1등에 몰빵 해주면 된다. 핵심은 1등에 몰빵하는 것이다. d가 3이상이면 1등부터 {d-1,d-2,....,1,0,0,....} 으로 최소 합을 이용해 d가지를 만들어주고 만약 합이 남는다면 1등에 더해주면 된다. 합이 남지 않았다면 최소 합을 이용해 d가지를 만들 수 없는 것이므로 잘못된 입력이다.

4. d가 1인 것이 조금 어려운데, 한가지만을 이용해 k개를 만들어야 하므로 p/k가 k개만큼 있어야 하는 것은 자명하다. 만약 k개를 만들 수 없다면? 대부분은 만들 수 있는데 p<k인 경우에만 안된다. 왜냐? p=0이면 전부 0으로 밀면 되고, p>0이면 1로 미는 것이 최선인데, 1을 k개만큼 만들지 못하면 안되기 때문이다.

5. 만약 k개를 만들고 남는다면? 남은 것들은 k번째부터 n번째까지 p/k로 만들어주면 된다. 이래도 비오름차순임은 만족하기 때문. 그럼 만들다 중간에 끊긴다면? 즉 나누어 떨어지지 않는다면? 중간에 p가 음수가 될 것이다. 이 값의 절댓값은 p/k보다 작다. 그러므로 마지막 p/k에 남은 음수값을 더해주면 된다. 아래 예시를 보자.

   // p = 11, n = 5, k = 2, d = 1
   p/k = 5
   5 5 5 0 0 // p=-4
   5 5 1 0 0 // a[2] += -4

   알아서 비내림차순이 되어준다.

6. 마지막으로 안전하게 유효체크를 한 번 더 해준다. k까지 서로 다른 수의 개수가 d가 아니면 잘못된 입력이다.

---

Pseudo code

if (d==2)
    a[0] = p
if (3<=d)
    a[0] = d-1
    for (i=1~d)
        a[i] = a[i-1]-1
    if (p<0) return 0
    a[0] += remain_p
if (d==1)
    if (p<k) return 0
    for (i = 0~n)
        a[i] = p/k
    a[last] += p

---

Source code

#include <iostream>
#include <vector>
using namespace std;

typedef vector<int> vec;
int n,p,k,d;

int cnt(vec s, int k) {
    int c=1;
    for (int i=0; i<k-1; i++)
        if (s[i]!=s[i+1])
            c++;
    return c;
}

int get() {
    vector <int> s(n,0);
    if (d==1) {
        if (p<k) return 0;
        int t=p/k;
        int i;
        for (i=0; i<n && 0<p; i++)
            s[i]=t, p-=t;
        s[i-1]+=p,p=0;
    } else {
        int td=d-1;
        for (int i=0; i<d && p; i++)
            s[i]=td, p-=td, td--;
        if (p<0) return 0;
        else s[0]+=p,p=0;
    }
    if (cnt(s,k)!=d) return 0;
    for (int i=0; i<n; i++)
        cout << s[i] << "\n";
    return 1;
}

int main() {
    cin>>n>>p>>k>>d;
    if (!get())
        cout << "Wrong information";
}