백준 1138번 한 줄로 서기

문제 링크입니다: https://www.acmicpc.net/problem/1138

간단한 그리디(greedy) 알고리즘 문제였습니다.

알고리즘은 아래와 같습니다.

1. 인덱스 번호대로 키가 부여되므로 이미 정렬되어 있는 상태입니다.

2. 왼쪽에 자신보다 키 큰 사람의 수를 입력받습니다.

3. 자기보다 키 큰 사람이 있는 경우 빈 자리를 지나칩니다.

4. 빈 자리이고 2번에서 입력받은 수만큼 키 큰 사람을 지나쳤다면 자신의 자리입니다.

#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;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~