백준 14222, 배열과 연산

개요

문제 링크
골드 5, Greedy
배열에 K씩 더해서 1부터 N까지 구성 가능한지 여부 출력하기

---

접근

1. 그리디한 인간이 되어보자. 우선 1부터 N까지의 수의 개수를 세어주는 것이 필요하다. 그리고 모든 수의 개수가 1이 되면 1을 출력해주면 된다.

2. K를 더한다 라고 생각하기보다 자신보다 K작은 수를 하나 뺏어온다 생각하자. 만약 없다면? 2K작은 수를 뺏어온다. 이렇게 위에서부터 찾아보며 2번 이상 등장한 값이 있으면 뺏어오면 된다.

3. 이게 왜 그리디한 최적이냐?하면 아래 예시를 보자.

   7 1
   1 2 3 3 5 5 7
   -> 1 2 3 5 5 6 7 (X)
   -> 1 2 3 3 5 6 7 (O)

   만약 6이 3을 뺏어서 6을 만들어 버리면 4가 가져올 것이 없다. 대신 5를 하나 뺏어와야 배열을 구성할 수 있다.

---

Pseudo code

count = 숫자갯수
for (i = n~1)
    if (count[i] = 0)
        for (j = n-k ~ 1)
            if (count[j] > 1)
                // 하나 뺏어온다.
                count[j]--, count[i]++

---

Source code

#include <iostream>
using namespace std;

int a[51], n,k,x;

bool check() {
    for (int i=1; i<=n; i++)
        if (a[i]!=1)
            return 0;
    return 1;
}

int main() {
    cin>>n>>k;
    for (int i=0; i<n; i++)
        cin>>x, a[x]++;

    for (int i=n; i>k; i--)
        if (!a[i])
            for (int j=i-k; j>=1; j-=k)
                if (a[j]>1) {
                    a[j]--, a[i]++;
                    break;
                }
    cout << check();
}