[Baekjoon] 1138번: 한 줄로 서기

🥅 문제

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

 

🔍 설계

큰 것을 먼저 배치하면, 선택의 폭이 많기 때문에 좋지 않다.

 

작은 것, 즉 앞에 있는 것부터 배치한다. 작은 것부터 배치하기 때문에 반복문으로 순회하면서 큰 것이 있는 상황은 고려하지 않아도 된다. 순회하는 과정에서 채워지지 않아서 0이라면, 자신보다 큰 사람의 수에서 1을 뺀다. 계속해서 빼다가 -1이 되면 배치한다.

 

👊 풀이

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, smaller;
vector<int> v(10);

int main(void)
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> smaller;
		for (int j = 0; j < n; j++) {
			if (v[j] > i || v[j] == 0) {
				smaller -= 1;
			}
			if (smaller == -1) {
				v[j] = i;
				break;
			}
		}
	}
	
	for (int i = 0; i < n; i++) {
		cout << v[i] << " ";
	}

	return 0;
}