이번 문제는 Greedy 알고리즘을 활용하여 해결하였다. 우선 규칙을 찾아보는 것이 중요했다.

• vi가 가질 수 있는 그렇고 그런 사이는 n-i개이다.
• 이를 0부터 n-1까지 반복하고 더하여 k를 만들어내는 문제이다.
• k의 범위가 0보다 크거나 같고, n-1보다 작거나 같다면 k+1의 값하나만 앞으로 가져오면 해결된다.
• k가 n과 2n-1사이라면 n-1과 남은 수 중 하나의 위치를 앞으로 옮기면 된다.
• k가 2n-2와 3n-6사이라면 n-1, n-2와 남은 수 중 하나의 위치를 옮기면 된다.
• k의 범위에 따라 계속해서 선택되는 수들을 늘리면 k의 n(n-1)/2까지의 경우를 모두 만들 수 있다.
• 즉, k를 n-1부터 비교하며 k가 이 수보다 크다면 k에 이 수를 빼주는 것을 반복한다.
• n-i가 필요하면 n-i+1을 배열의 제일 왼쪽부터 차례대로 채워 나가고 이 작업이 끝나면 남은 수를 오름차순으로 비어있는 곳에 배치해준다.
• visited배열은 수를 사용한 것을 체크한다.

Code

#include <iostream>
#include <cstring>
#define MAX 4243
using namespace std;

int n, k;
int v[MAX];
bool visited[MAX];

void Input(){
    cin>>n>>k;
    memset(v, 0, sizeof(v));
    memset(visited, false, sizeof(visited));
}

void Solution(){
    int end=n;
    int idx=1;
    while(k){
        if(k>=end-1){
            k-=(end-1);
            v[idx]=end;
            idx++;
            visited[end]=true;
        }
        end--;
    }
    int num=1;
    for(int i=1; i<=n; i++){
        if(v[i]!=0) continue;
        while(visited[num])
            num++;
        v[i]=num++;
    }
}

void Solve(){
    for(int i=1; i<=n; i++){
        cout<<v[i]<<" ";
    }
    cout<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    Solve();
    return 0;
}