백준 1276번: PLATFOME

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

곂치지 않는 플랫폼들에 기둥을 세울 때, 기둥의 길이의 합을 구하는 문제이다.

문제의 설명처럼 기둥은 플랫폼 양 끝쪽에 세우나 완전한 끝이 아닌 면에 세우기 때문에 단순히 해당 좌표와의 높이를 구하면 오류가 발생한다. 첫번째 플랫폼이 높이 1, 가로가 1에서 5 까지라면, [1, 2], [2, 3], [3,4], [4,5] 라는 4개의 구간이 되고 [1, 2], [4, 5]에 기둥을 세우며, 다음 플랫폼이 높이 2, 가로 5부터 시작하더라도 [5, 6]에 기둥을 세우기 때문에 이는 첫번째 플랫폼에 영향을 받지 않게 된다. 반대의 경우도 문제의 그림처럼 첫번째 기둥과 두번째 기둥이 영향을 받지 않게 되어 그대로 바닥에 기둥을 세우게 된다.

 

풀이는 높이가 낮은 플랫폼 부터 높은 플랫폼까지 양끝의 위치에서 아래로 가장 가까운 플랫폼 혹은 바닥에 기둥을 세워서 길이를 구하고 높이를 최신화 하는 방식으로 구성하였다. 이를 위해 class, PriorityQueue를 이용하였다.

static class Platform implements Comparable<Platform> {
    
    int y, start, end;
    
    public Platform(int y, int start, int end) {
        this.y = y;
        this.start = start;
        this.end = end;
    }
    
    @Override
    public int compareTo(Platform o) {
        return this.y - o.y;
    }
}

 

Queue<Platform> pq = new PriorityQueue<>();
StringTokenizer st;
for (int i = 0; i < n; i++) {
    st = new StringTokenizer(br.readLine());
    int y = Integer.parseInt(st.nextToken());
    int start = Integer.parseInt(st.nextToken()), end = Integer.parseInt(st.nextToken());
    pq.add(new Platform(y, start, end));
}

 

 

높이 계산은 (현재 높이 - 시작지점 높이) 와 (현재 높이 - (종료지점-1)의 높이)를 누적하며, 시작지점부터 종료지점 -1까지 현재 지점으로 높이를 업데이트해 주었다.

int[] board = new int[10001];
long length = 0;
while (!pq.isEmpty()) {
    Platform current = pq.remove();
    length += current.y - board[current.start];
    length += current.y - board[current.end - 1];
    for (int i = current.start; i < current.end; i++) {
        board[i] = current.y;
    }
}

 

 

최종 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class PLATFORME1276 {
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        Queue<Platform> pq = new PriorityQueue<>();
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int y = Integer.parseInt(st.nextToken());
            int start = Integer.parseInt(st.nextToken()), end = Integer.parseInt(st.nextToken());
            pq.add(new Platform(y, start, end));
        }
        br.close();
        int[] board = new int[10001];
        long length = 0;
        while (!pq.isEmpty()) {
            Platform current = pq.remove();
            length += current.y - board[current.start];
            length += current.y - board[current.end - 1];
            for (int i = current.start; i < current.end; i++) {
                board[i] = current.y;
            }
        }
        System.out.print(length);
    }
    
    static class Platform implements Comparable<Platform> {
        
        int y, start, end;
        
        public Platform(int y, int start, int end) {
            this.y = y;
            this.start = start;
            this.end = end;
        }
        
        
        @Override
        public int compareTo(Platform o) {
            return this.y - o.y;
        }
    }
}