BOJ 20921 : 그렇고 그런 사이

• 문제 링크 : boj.kr/20921
• 난이도 : S1
• 태그 : 해 구성하기, 그리디

20921번: 그렇고 그런 사이

코드

#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, k;
    cin >> n >> k;
    
    vector<int> arr;
    for(int i = n-1; i > 0; i--) {
        if(k >= i) {
            arr.emplace_back(n-1-i);
            k -= i;
        }
    }

    int num = 1;
    int idx = 0;
    for(int i = 0; i < n; i++) {
        if(arr.size() > idx && i == arr[idx]) {
            cout << n - idx << " ";
            idx++;
        }
        else {
            cout << num << " ";
            num++;
        }
    }

    return 0;
}

---

풀이

i번 사람과 그 오른쪽에 있는 모든 사람이 그렇고 그런 사이일 떄, i번 사람의 오른쪽에 있는 사람끼리 쪽지를 서로 바꾸더라도 i번 사람과 그렇고 그런 사이는 유지된다.

i번 사람에게 그 오른쪽에 있는 모든 사람의 정수보다 큰 정수의 쪽지를 준다면 n-i-1개의 그렇고 그런 사이가 생겨난다.

 

1번부터 시작하여, i번 사람에 대해 남은 필요한 그렇고 그런 사이의 수와 i번 사람과 그 오른쪽의 사람의 수를 비교하여 i번 사람에게 오른쪽의 모든 사람들보다 큰 정수를 줄지 결정한다.

 

그렇게 결정된 사람들에게 왼쪽부터 가장 큰 수를 순서대로 주고 그렇지 않은 사람들에게는 왼쪽부터 가장 작은 수를 순서대로 준다.