[백준] 1138번 한 줄로 서기 (C++)

문제

 

https://www.acmicpc.net/problem/1138

---

풀이

이 문제는 그리디/구현 문제로, 입력과 동시에 최적의 해를 찾아 순서를 배치한다.

 

2 1 1 0이 입력됐다면, 

1. 2 입력, 0을 두 번 건너 뜀 ▶ 0 0 2 0
2. 1 입력, 0을 한 번 건너 뜀 ▶ 0 1 2 0
3. 1 입력, 0을 한 번 건너 뜀 ▶ 0 1 2 3
4. 0 입력, 0을 건너 뛰지 않음 ▶ 4 1 2 3

#include <iostream>

// https://www.acmicpc.net/problem/1138

using namespace std;

int main() {
    int n, p;
    int arr[11] = { 0, };

    cin >> n;

    for (int i = 0; i < n; i++) {
        cin >> p;

        int count = p;
        for (int j = 0; j < n; j++) {
            if (count == 0 && arr[j] == 0) {
                arr[j] = i + 1;
                break;
            }
            
            if (arr[j] == 0) {
                count--;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }

    return 0;
}