한 줄로 서기 << 문제 클릭!
: N명의 사람들이 고정된 자리로 한 줄로 선다.
: 사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지 만을 기억
: N명의 사람이 있고 사람들의 키는 1부터 N까지 모두 다르다.
: 줄을 어떻게 서야 하는지 출력하는 프로그래믈 작성하라
✅ 그리디로 생각했을 때 최적의 상황은?
키가 작은 사람부터 최대한 왼쪽의 사람 수 만큼 앞자리를 선택하는 것!
#include <bits/stdc++.h>
using namespace std;
int main(void) {
int N;
cin >> N;
int arr[10];
fill(arr,arr+10,11); // 11로 초기화
for (int i = 1; i <= N; i++) {
/*초기화*/
int temp = 0;
int count = 0; // 나보다 왼쪽에 있는 사람 세기
int j = 0; // 인덱스
cin >> temp; // 숫자를 받기
while (true) {
if (count == temp) { // count와 temp가 같을 때
if (arr[j] != 11) { // 빈 자리가 아니면
j++;
}
else { // 빈자리면
break;
}
}
else { // count와 temp가 같지 않을 때
if (arr[j] == 11) { // 자기 보다 큰 애가 있을때
count++;// 큰 애 count
j++; // 인덱스 증가
}
else { // 자기보다 큰 애가 아니면
j++; //인덱스 증가
}
}
}
arr[j] = i; // 할당
}
for (int i = 0; i < N; i++) {
cout << arr[i] << " ";
}
}
다른 분들의 풀이 출처
#include <iostream>
using namespace std;
const int MAX = 10;
int N;
int line[MAX];
int main(void)
{
cin >> N;
//키 순서
for (int i = 0; i < N; i++)
{
int left;
cin >> left;
//줄을 순회하는데
for (int j = 0; j < N; j++)
//자신의 자리가 마련되어있고 키 큰 사람들을 다 지나쳤다면
if (left == 0 && line[j] == 0)
{
line[j] = i + 1;
break;
}
//키 큰 사람이 있는 곳을 지나친다
else if (line[j] == 0)
left--;
}
for (int i = 0; i < N; i++)
cout << line[i] << " ";
cout << "\n";
return 0;
}