[1138] 한 줄로 서기

문제

1138번: 한 줄로 서기

 

 

🔎 해결 방법 

현재 상태에서 최선인 것만 보는 그리디 알고리즘을 사용해서 풀어야 하는 문제이기 때문에 

말 그대로 모든 것을 현재 상황 기준으로 결정하면 된다.

 

예를 들어 줄을 서야 하는 사람의 수가 5명이고, 자신보다 왼쪽에 있는 사람 중 키 큰 사람의 수를 담고 있는 left배열이 다음과 같이 주어진다고 가정하자.

우선 키가 1인 사람부터 보면 1인 사람의 왼쪽에는 키가 1보다 큰 사람이 2명 있어야 한다. 

 

그러면 키카 1인 사람은 왼쪽에 빈칸이 2개 있어야 하므로, 앞에서부터 3번째 자리에 서면 된다.

 

키가 2인 사람은 자신 보다 큰 사람이 왼쪽에 1명만 있어야 하므로

왼쪽에 빈칸 1개를 두고 그 다음에 서면 된다.

 

키가 3인 사람은 자신보다 왼쪽에 있는 키큰 사람의 수가 0명이므로

빈칸이 없어야 한다.

 

키가 4인 사람은 자신보다 왼쪽에 있는 키큰 사람의 수가 1명이므로 빈칸 한개를 두고 그 다음 자리에 서면 된다.

 

키가 5인 사람은 자신보다 왼쪽에 있는 키큰 사람의 수가 0명이므로 빈칸 없이 바로 서면 된다. 

그리고 어차피 자신이 키가 제일 크기 때문에 그냥 남은 자리에 서면 된다.

 

즉, 자신 보다 왼쪽에 있는 키 큰 사람의 수는 현재 자기가 서야 할 자리 앞에 있는 빈칸의 개수이다.

 

 

💡 내 코드(C++) 

// [1138] 한 줄로 서기
// https://www.acmicpc.net/problem/1138

#include <iostream>
using namespace std;

int main(void)
{
    int n; // 사람의 수
    int left[11], line[11] = {0, }; // 왼쪽에 있는 키 큰 사람의 수, 줄을 선 순서
    cin >> n;
    for(int i = 1 ; i <= n ; i++) {
        cin >> left[i];
    }
    
    for(int i = 1 ; i <= n ; i++) {
        int blank = 0;
        
        for(int j = 0 ; j < n ; j++) {
            if(line[j] == 0) {
                blank++;
                
                if(blank == (left[i] + 1)) {
                    line[j] = i;
                    break;
                }
            }
        }
    }
    
    for(int i = 0 ; i < n ; i++) {
        cout << line[i] << " ";
    }
}