[백준 24025번] 돌의 정령 줄세우기 (C++)

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

돌의 정령의 무리의 키가 4 1 5 2 3 이라면 왼쪽수터 시야 점수는 2 0 INF 0 INF 가 된다. 자신의 무리보다 키가 큰 무리 전까지의 돌의 정령 무리 수가 시야 점수가 된다.

 

문제에서 돌의 정령 무리수와 동일한 개수만큼의 숫자가 주어진다. 주어진 숫자가 A(A>0)일 경우 해당 숫자가 주어진 인덱스의 돌의 정령의 시야점수가 A이상이 되도록, 주어진 숫자가 -A(-A<0)일 경우는 해당 숫자가 주어진 인덱스의 돌의 정령의 시야점수가 A이하가 되도록 1~N까지의 돌의 정령을 배치하라는 문제이다.

 

★Point

1. 마지막에 배치되는 돌의 정령의 시야점수는 항상 INF이다.

2. 돌의 정령의 무리가 N~1까지 내림차순으로 배치되면, 모든 돌의 정령의 무리의 시야점수는 INF이다.

 

돌의 정령의 시야점수가 딱 A가 되게 만드는 것이 아니라 A이상 -A이하로 만들어도 되기 때문에 돌의 정령을 내림차순으로 배열하여 시야를 INF로 만들고 후에 -A인 부분을 처리하는 식으로 생각하면 된다.

처리는 내림차순으로 배치한 후에 배열A에서 음수인 부분의 인덱스와 다음 인덱스의 원소까지 reverse를 해주면 된다.

그럼 음수인 부분의 돌의정령은 시야가 항상 0이 되서 조건을 만족시킨다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, arr[70001], stone[70001];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> arr[i];
        stone[i] = n+1-i;
    }

    int idx = 1;
    bool flag = true, check = false;
    vector<int> negatives;
    while(idx <= n){
        if(arr[idx] < 0){
            if(idx == n) flag = false;
            negatives.push_back(idx);
            check = true;
            idx++;
            continue;
        }
        if(!check) {
            idx++;
            continue;
        }
        negatives.push_back(idx);
        int start = negatives[0], end = negatives.back();
        reverse(stone+start, stone+end+1);
        negatives.clear();
        check = false;
        idx++;
    }
    if(flag){
        for(int i = 1; i <= n; i++) cout << stone[i] << " ";
    }
    else cout << -1;
}

 

 

+코드포스 스타일의 문제(구성적)

++돌의 정령은 매우 귀엽담.