BOJ : 1138 한 줄로 서기

---

[BOJ 1138(S2) 리뷰]

아 그리디 너무 어렵다 ..

그리디인걸 알고 풀어도 잘 안풀리는데 코테에서 그리디임을 발견하고 풀 수 있을지 모르겠다.

 

키가 1부터N까지인 사람들이 있다. 이 사람들은 각각 왼쪽에 자기보다 키 큰 사람이 몇명있었는지 기억한다.

우리는 그 정보를 토대로 줄을 세워야 한다.

입력이

2 1 1 0 으로 주어지면

1보다 키 큰사람이 왼쪽에 2명,

2보다 키 큰사람이 왼쪽에 1명,

3보다 키 큰사람이 왼쪽에 1명,

4보다 키 큰사람이 왼쪽에 0명 이고 이때 올바르게 줄을세우면 4 2 1 3이 된다.

이제 이걸 어떻게 푸느냐가 문제다. 물론 완전탐색으로도 풀 수있으나 문제의 본질은 아니라 생각한다.

 

이 문제는 키가 가장 작은 1부터 시작한다.

1보다 키가 작은 사람은 없으므로 1의 왼쪽에 N명이 있다면 1의 위치는 N+1임이 자명하다.

그 다음 키가 2인사람은 왼쪽에 N명이 있다면 2의 왼쪽에 최소 N개의 빈 공간이 있어야 한다.

2는 왼쪽으로부터 N개만큼 떨어진 곳으로 이동하여 그곳이 만약 비어있다면 (자신보다 작은사람이 앞에 없음) 그자리가 2의 위치가 된다. 만약 그 자리가 비어있지 않다면 그것은 이미 자신보다 작은 키가 위치한 곳이므로 한칸 더 이동하면 된다.

 

위 로직은 키가 작은사람부터 시작하기에 가능하다.

내 뒤에 나오는 사람은 반드시 자기 보다 키가 크며, 자기보다 앞서 나왔던 사람은 반드시 자기보다 키가 작기에 성립하는 구조이다.

---

#include <bits/stdc++.h>
using namespace std;


int main(void)
{
	int N;
	int ans[10] = { 0, };
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		int taller;
		cin >> taller;

		int idx = 0;
		int cnt = 0;
		while (taller || ans[idx])
		{
			if (!ans[idx]) 
				taller--;
			idx++;
		}
		ans[idx] = i;
	}

	for (int i = 0; i < N; i++)
		cout << ans[i] << ' ';

	
}