백준] 1138 - 한 줄로 서기

시간 제한 : 2초

메모리 제한 : 128MB

입력

첫째 줄에 사람의 수 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 키가 1인 사람부터 차례대로 자기보다 키가 큰 사람이 왼쪽에 몇 명이 있었는지 주어진다. i번째 수는 0보다 크거나 같고, N-i-1보다 작거나 같다.

출력

첫째 줄에 줄을 선 순서대로 키를 출력한다.

소스코드

#include <iostream>
using namespace std;
int main(void)
{
	int n;
	int arr[10], ans[11] = { 0, };
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
	ans[arr[0] + 1] = 1;
	for (int i = 1; i < n; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= n; j++)
		{
			if (cnt == arr[i] && ans[j] == 0)
			{
				ans[j] = i + 1;
				break;
			}
			if (ans[j] > i + 1 || ans[j] == 0)
				cnt++;
		}
	}
	for (int i = 1; i <= n; i++)
		cout << ans[i] << ' ';
}

Tip

어느 시점에 사람을 배치해야 하는지 애를 조금 먹었는데, 주어진 숫자(자기보다 키가 큰 사람의 숫자)와 같아지는 순간에 배치하려는 곳이 공석이면 바로 배치하는 식으로 접근하면 된다. 조건을 충족하는대로 바로 배치하는 점에서 그리디로 분류한 듯. 수학적으로 접근하는 방법은 잘 모르겠다.