[BOJ]1597:矢印を描く

質問する

位置が直線上の0、1、2...等非負の数の整数を一定の間隔で右に置きます.これらの位置の各位置には点があります(<図1>).指定点の位置が違います.2点間の距離は、2点位置の数の差を表します.<図1>には4つの点が与えられ、点aとbの距離は3である.

＜図1＞
各点にN色のうちの1つがあります.私服、色は1からNの数字で表します.
各点pについて、pから始まる直線矢印を用いて別の点qに接続しようとする.ここで、点qはpのような色の点の中でpに最も近い点であるべきである.最近の点が2つ以上あれば、勝手に1つ選んでください.
各点について、常に同じ色の異なる点が存在します.したがって、上記の条件を満たすqまで、各点pから常に矢印を描くことができる.
例えば、点を順次対(位置、色)と表記する場合、a=(0,1)、b=(1,2)、c=(3,1)、d=(4,2)、e=(5,1)と呼ぶ.
以下の<図2>にこれらの点を表示します.ここで、白は1に相当し、黒は2に相当する.

＜図2＞
上記の条件で矢印を描画すると、図3に示すように、点aの矢印がcに接続されます.点bとdの矢印は、それぞれdとbに接続されている.また、点cとeの矢印は、それぞれeとcに接続されている.したがって、すべての矢印の長さは、3+3+2+2=13です.

<図3>
ポイントの位置と色を指定すると、ライタはすべてのポイントから始まる矢印の長さとを出力します.

- 시간 제한 : 2초
- 메모리 제한 : 512MB

方法

この問題を解決するには、同じ色の点をまとめ、同じ色の点間の最小距離を求めるために位置順にソートする必要があります.したがって、ポイントクラスはComparableインタフェースを実装する必要がある.

static class Point implements Comparable<Point> {
    int position;
    int color;

    Point(int position, int color) {
        this.position = position;
        this.color = color;
    }

    /**
     * @param other 정렬을 할 때 비교할 다른 점
     * @return this.color - other.color,
     * 둘의 색깔이 같다면 this.position - other.position
     */
    public int compareTo(Point other) {
        if (this.color == other.color) {
            return this.position - other.position;
        }

        return this.color - other.color;
    }
}

同じ色の点を集約するには、compareToで、まず比較条件の色を比較し、同じ色であれば位置を昇順に並べます.整列条件が実施されている以上、1つの点の前の点と次の点のより短い距離を求める方法を実施する必要がある.

static class Point implements Comparable<Point> {
    int position;
    int color;

    ...

    /**
     * @param previous 이전 점
     * @param next 다음 점
     * @return 이전 점과 다음 점 중 더 가까운 길이
     */
    public int getShortestDistance(Point previous, Point next) {
        int leftDistance = this.getDistance(previous);
        int rightDistance = this.getDistance(next);

        // 이전 점과 거리를 구할 수 없는 경우
        if (leftDistance == 0) return rightDistance;

        // 다음 점과 거리를 구할 수 없는 경우
        if (rightDistance == 0) return leftDistance;

        // 두 점들의 거리 중 더 가까운 것을 반환
        return Integer.min(leftDistance, rightDistance);
    }

    /**
     * @param other 현재 점과 비교할 다른 점
     * @return 색깔이 같은 다른 점이 주어지면 거리를 반환, 그렇지 않으면 0을 반환
     */
    private int getDistance(Point other) {
        // 비교할 점이 없으면 0을 반환
        if (other == null) return 0;

        // 서로 색깔이 다르다면 0을 반환
        if (this.color != other.color) return 0;

        // 현재 점과 다른 점의 거리를 반환
        return Math.abs(this.position - other.position);
    }
}

getDistanceは、現在の点と異なる点の距離を求める方法である.異なる点または異なる色がない場合、距離を求めることができないため、0を返します.色が同じ場合、2点間の距離を返します.getShortestDistanceは、前の点と次の点を受け入れ、getDistanceを使用して現在の点からの距離を求め、より短い距離を返す.leftDistanceまたはrightDistanceに無効な距離がある場合は有効距離を返し、両方が無効な場合は0を返します.
さらに,上点と下点の間のより短い距離を求める方法を実施し,以下の方法で問題を解決した.

コード#コード#

import java.io.*;
import java.util.*;

public class Main {

    static int n;
    static Point[] points;
    static int total = 0;

    static class Point implements Comparable<Point> {
        int position;
        int color;

        Point(int position, int color) {
            this.position = position;
            this.color = color;
        }

        /**
         * @param other 정렬을 할 때 비교할 다른 점
         * @return this.color - other.color,
         * 둘의 색깔이 같다면 this.position - other.position
         */
        public int compareTo(Point other) {
            if (this.color == other.color) {
                return this.position - other.position;
            }

            return this.color - other.color;
        }

        /**
         * @param previous 이전 점
         * @param next 다음 점
         * @return 이전 점과 다음 점 중 더 가까운 길이
         */
        public int getShortestDistance(Point previous, Point next) {
            int leftDistance = this.getDistance(previous);
            int rightDistance = this.getDistance(next);

            // 이전 점과 거리를 구할 수 없는 경우
            if (leftDistance == 0) return rightDistance;

            // 다음 점과 거리를 구할 수 없는 경우
            if (rightDistance == 0) return leftDistance;

            // 두 점들의 거리 중 더 가까운 것을 반환
            return Integer.min(leftDistance, rightDistance);
        }

        /**
         * @param other 현재 점과 비교할 다른 점
         * @return 색깔이 같은 다른 점이 주어지면 거리를 반환, 그렇지 않으면 0을 반환
         */
        private int getDistance(Point other) {
            // 비교할 점이 없으면 0을 반환
            if (other == null) return 0;

            // 서로 색깔이 다르다면 0을 반환
            if (this.color != other.color) return 0;

            // 현재 점과 다른 점의 거리를 반환
            return Math.abs(this.position - other.position);
        }
    }

    public static void main (String[] args) {
        input();
        func();
        System.out.println(total);
    }

    static void input() {
        Scanner scanner = new Scanner(System.in);

        n = scanner.nextInt();
        points = new Point[n];

        for (int i = 0; i < n; ++i) {
            points[i] = new Point(
                    scanner.nextInt(),
                    scanner.nextInt()
            );
        }

        scanner.close();
    }

    static void func() {
        Arrays.sort(points);

        // 2개 미만의 점이 존재할 경우 화살표를 그릴 수 있는 
        // 경우가 존재하지 않으므로
        if (n < 2) return;
        
        // 가장 처음 점의 화살표 길이
        total += points[0].getShortestDistance(null, points[1]);

        // for 문을 이용하여 이전 점과 다음 점 중 더 가까운 점에 화살표를 그린다.
        for (int i = 1; i < n - 1; ++i) {
            total += points[i].getShortestDistance(points[i - 1], points[i + 1]);
        }

        // 마지막 점의 화살표 길이
        total += points[n - 1].getShortestDistance(points[n - 2], null);
    }
}