[BOJ 1138] 한 줄로 서기(C++).

https://www.acmicpc.net/problem/1138

1138번: 한 줄로 서기

 

N번째 사람부터 놓기 시작하면, 현재의 상황만 보고 순서를 고려하면 된다.(그리디)

 

 

 

i번째를 놓을 때, i + 1번째부터 N까지 놓아졌다면 모든 수는 i보다 크므로, 아래의 코드를 작성할 수 있다.

 

 

 

해설코드(C++).

#include <iostream>
#include <vector>
 
using namespace std;
 
int N;
int val;
vector<int> v;
vector<int> result;
 
int main() {
    cin >> N;
    for(int i = 1; i <= N; i++){
        cin >> val;
        v.push_back(val);
    }
 
    for(int i = v.size() - 1; i >= 0; i--){
        int val = v[i];
        vector<int>::iterator it;
        for(it = result.begin(); it != result.end(); it++){
            if(val == 0){
                break;
            }else
                val -= 1;
        }
        result.insert(it, i + 1);
    }
 
    for(int i = 0; i < result.size(); i++){
        cout << result[i] << " ";
    }
    cout << endl;
 
    return 0;
}