[ 백준 ] 9011 / 순서

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
167/228
post-thumbnail
post-custom-banner

# Appreciation

/*
 * Problem :: 9011 / 순서
 *
 * Kind :: Math
 *
 * Insight
 * - 입력으로
 *   10
 *   0 0 0 2 0 1 6 7 6 9
 *   가 주어졌다고 하자 <= 예제 입력 1
 *   + r_i 가 S 의 부분 순서 {s_1 ~ s_(i-1)} 중에서 s_i 보다 작은 수의 개수라면...
 *     s_N 은 (r_N + 1) 일려나?
 *     # 맞다! 그렇지 않으면 논리적으로 옳지 않다!
 *       s_i != s_j 이고 1 <= s_i <= N 이라면,
 *       순서 S 는 1~N 으로 이루어진 순열 중 하나인데,
 *       r_N 은 s_N 보다 작은 수의 개수이므로 r_N = (s_N - 1) 일 수밖에 없다!!!
 *       그렇기에 위의 입력에서는 r_N 이 9 니까 s_N 은 10 일 수밖에 없다!!!
 *       -> 거꾸로 하나씩 찾아가면 되겠다!!!
 *
 * - 순서 S 를 순서 R 통해 거꾸로 찾아가는데...
 *   ? ? ? ? ? ? ? 8 7 10 이 되는데,
 *   예제 출력 1 의 답은
 *   * * * * * * * 9 7 10 이다
 *   + 놓친 부분이 있는 것 같다
 *     왜 s_8 에 8 이 아니라 9 가 들어가는 걸까?
 *     # s_9 에 7 을 썼기 때문이다!
 *       그러니 8 보다 작은 수의 개수는 7이 아니라 6이다
 *       -> 1~N 의 수들중 이전에 사용된 수들을 추적해야 된다!!!
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <cstring>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        int N; cin >> N;
        int R[N];
        for (int i=0; i<N; i++) {
            cin >> R[i];
        }

        // Process
        bool isUsed[N+1]; /* isUsed[i] = i 가 사용되었으면 true, 그렇지 않으면 false */
        memset(isUsed, false, sizeof(isUsed)); /* 초기화 */

        int S[N];
        bool isPossible = true; /* R 로부터 S 를 만들 수 있는지 여부 */
        for (int i=N-1; i>=0; i--) {
            int s = R[i]+1; /* s_i 의 초기 후보 s */
            for (; s<=N; s++) { /* s 부터 N 까지 검사 */
                if (isUsed[s]) continue; /* s 가 사용되었으면 넘어감 */
                int cnt = 0; /* s 보다 작은 수의 개수 */
                for (int k=1; k<s; k++) {
                    /* s 보다 작고 사용되지 않은 수이면 */
                    if (not(isUsed[k])) { cnt++; } /* cnt 증가 */
                }

                /* s 보다 작은 수의 개수와 R[i] 가 같으면 */
                if (cnt == R[i]) {
                    S[i] = s; /* s 의 값이 바로 s_i */
                    isUsed[s] = true; /* s 사용 처리 */
                    break; /* 찾았으므로 더이상의 탐색은 의미없음 */
                }
            }

            /* N 까지 탐색했으나 적합한 s_i 의 값을 찾지 못했으면
             * (for 문의 s++ 로 인해 s=N+1 이 된 상태) */
            if (s > N) {
                isPossible = false; /* R 로부터 S 만들기 불가능 */
                break; /* 불가능하므로 더이상의 탐색은 의미없음 */
            }
        }

        // Control : Output
        if (not(isPossible)) {
            cout << "IMPOSSIBLE" << endl;
        } else {
            for (int i=0; i<N; i++) {
                cout << S[i] << ' ';
            } cout << endl;
        }
    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이
post-custom-banner

0개의 댓글