백준 24025번: 돌의 정령 줄세우기 (Java)

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

24025번: 돌의 정령 줄세우기

 

 

 

 

 

 

 

 

---

 

풀이

전형적인 코드포스 스타일의 구성적/그리디 문제입니다. 쌩 브루트포스는 O(N!)일테니 절대 안되며, 적당히 가지치기한다고 해도 O(N^2) 이하로 줄이기가 쉽지 않아보입니다. 그러다 보면, '최적의 배치가 존재하지 않을까?'와 같은 생각에 도달하게 됩니다(그리디 말고는 생각나는게 없으니...). 그리디하게 찾아보도록 합니다.

 

1-based를 기준으로, 1 <= i <= N-1번째 칸에 대하여, i = 1부터 N-1까지 반복문을 수행하면서

A_i > 0: 현재 남은 돌의 정령 중 가장 키가 큰 정령을 배치합니다.

A_i < 0: 현재 남은 돌의 정령 중 가장 키가 작은 정령을 배치합니다.

마지막으로 N번째 자리에는 남은 돌의 정령 1마리를 배치합니다.

 

이런 식으로 배치하면, 1 <= i <= N-1에 대하여

A_i > 0인 경우: i번째 돌의 정령의 오른쪽에 i번째 돌의 정령보다 키가 큰 돌의 정령이 없기에, 시야 점수는 10^9이 됩니다. 10^9 > N이므로 언제나 조건을 만족합니다.

A_i < 0인 경우: 바로 오른쪽에 키가 큰 돌의 정령이 붙기에, 시야 점수는 1이 됩니다. |A_i| >= 1이므로, 언제나 조건을 만족합니다.

그리고, N번째 돌의 정령의 시야 점수는 무조건 10^9이기에, A_N이 음수라면 조건을 만족하는 배치가 불가능하며, A_N이 양수라면 조건을 만족하는 배치가 가능합니다.

 

 

코드

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int l = 1, r = N;
        for (int i = 0; i < N-1; i++) {
            if (Integer.parseInt(st.nextToken()) > 0) {
                sb.append(r+" ");
                r--;
            } else {
                sb.append(l+" ");
                l++;
            }
        }
        
        if (Integer.parseInt(st.nextToken()) < 0) {
            System.out.println(-1);
        } else {
            sb.append(r+"");
            System.out.println(sb.toString());
        }
    }
}
 

 

 

P.S.

집에 있는 돌의 정령 인형