[백준문제풀이] 1138 한 줄로 서기

 

풀이일시 : 2020-09-02

​

 

문제 :

N명의 사람들은 매일 아침 한 줄로 선다. 이 사람들은 자리를 마음대로 서지 못하고 오민식의 지시대로 선다.

어느 날 사람들은 오민식이 사람들이 줄 서는 위치를 기록해 놓는다는 것을 알았다. 그리고 아침에 자기가 기록해 놓은 것과 사람들이 줄을 선 위치가 맞는지 확인한다.

사람들은 자기보다 큰 사람이 왼쪽에 몇 명 있었는지만을 기억한다. N명의 사람이 있고, 사람들의 키는 1부터 N까지 모두 다르다.

각 사람들이 기억하는 정보가 주어질 때, 줄을 어떻게 서야 하는지 출력하는 프로그램을 작성하시오.

​

 

입력:

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

ex)

4 //사람의 수

2 1 1 0 //키가 1인사람의 왼쪽에는 자기보다 키큰사람이 두명

키가 2인 사람의 왼쪽에는 자기보다 키큰사람이 한명

키가 3인 사람의 왼쪽에는 자기보다 키큰사람이 한명

키가 4인 사람의 왼쪽에는 자기보다 키큰사람이 없다.

​

 

출력:

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

ex)

4 2 1 3

​

 

풀이 :

사람들을 키 순서대로 세우면 되는 문제이다.

자신보다 왼쪽에 있는 사람의 숫자를 입력으로 넣는다.

모든 사람에 대해서 왼쪽부터 하나씩 살펴보며 자신이 들어갈 수 있는 위치를 고르면 된다.

 

그리디알고리즘 분류

dbstndi6316.tistory.com/62

[기본문제풀이] greedy 알고리즘

 

#include <iostream>

using namespace std;
int d[11];

int main() {
	int n;
	cin >> n; //사람의 수 n명
	for (int i = 1; i <= n; i++) {
		int x;
		cin >> x; //자기보다 키가 큰 사람이 왼쪽에 몇 명 있었는지 i=1:x=2 , 2:1, 3:1, 4:0 
		int count = 0;
		//사람과 위치 계속 반복하며 빈 위치에 넣어주면된다.
		for (int j = 1; j <= n; j++) { //사람이 서있는 위치
			if (count == x && d[j] == 0) {
				d[j] = i; //d[3]=1 d[2]=2 d[4]=3 d[1]=4 //1번사람은 3번위치에(두명이앞에있으니)
// 2번사람은 2번위치에 
// 3번사람은 1번안되고 3번안되고 2번안되니깐 4번위치에 
// 4번사람은 1번위치에
				break;
			}
			if (d[j] == 0)
				count++;
		}
	}
	for (int i = 1; i <= n; i++) {
		printf("%d ", d[i]);
		//줄을 선 순서대로 키를 출력한다.
	}
	return 0;
}