백준 2459 철사 자르기 자바(java)

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

2459번: 철사 자르기

 

풀이 방법

처음엔 격자판을 생성하여 교차점을 지나가는 곳마다 체크해준 후 길이를 구해주어야 하나 생각했지만, 철사가 겹쳐지는 것은 어떻게 구분할 것이며.. 어떤 길을 따라왔는지 구분이 매우 힘들 것 같아 이 방법은 아니라고 생각했다. 그래서 순서대로 교차점을 지나면서 그때 그때 철사 조각을 생성해주는 방법으로 구현했다. 철사 정보는 Wire 클래스를 생성하여 철사 조각의 길이를 저장해주도록 하였다. 

 

풀이 흐름

1. 생성된 철사 조각을 저장할 수 있도록 Stack을 생성한 후 길이 0인 Wire 객체를 처음 삽입한다.
2. 현재 위치를 curX = 1, curY = 1 로 둔 후 순서대로 교차점을 순회한다.
3. 현재 위치와 다음 교차점의 x 범위를 체크하여 그 사이에 자르는 직선 I가 존재하는지 확인한다.
4. 존재하지 않으면 Stack 에서 peek 한 마지막 Wire 객체에 두 좌표 사이의 길이를 더한다. 
5. 존재한다면 조각이 나누어지므로 나누어진 두 개의 조각을 구해주어야 한다.
   • 첫번째는 Stack 에서 peek한 마지막 Wire 객체 길이에 현재 위치 ~ 직선 I까지의 거리를 더한다.
   • 두번째는 새로운 Wire 객체를 생성하여 직선 I ~ 다음 교차점까지의 길이를 저장하여 삽입한다.
6. 현재 위치 curX, curY 를 교차점 위치로 갱신한다.
7. K번째 교차점까지 3~6번을 반복한 후, 교차점을 (1, 1) 로 하여 한 번 더 수행하여 (1, 1)에 연결한다.
8. 모든 철사 생성 후 Stack 에 저장된 철사의 길이 중 최댓값을 구한다.
   • 이때, 첫번째 철사와 마지막 철사는 붙여지므로 둘의 길이를 더한 후 최댓값을 갱신해주어야 한다.

 

주의할 점!

만약, 조각이 반으로 잘라졌을 때의 길이를 0.5로 그대로 더해준다면 길이 변수의 타입을 실수형 타입을 써주어야 한다. 그리고 N이 최대 1,000,000 이고 K가 최대 100,000 이므로 최악의 경우 약 10^11 의 길이가 나올 수 있다. 따라서 범위가 큰 타입인 double 형으로 길이를 구한 후 long 형으로 형 변환하여 출력해주었다.

 

 

코드

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

public class Main {

    static class Wire {
        double length;

        public Wire(double length) {
            this.length = length;
        }
    }

    static int N, K, I;
    static int curX = 1, curY = 1; // 현재 교차점 위치
    static Stack<Wire> wires = new Stack<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        K = Integer.parseInt(br.readLine());
        int[][] curves = new int[K][2];

        for(int i=0; i<K; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            curves[i][0] = Integer.parseInt(st.nextToken());
            curves[i][1] = Integer.parseInt(st.nextToken());
        }
        I = Integer.parseInt(br.readLine());

        wires.add(new Wire(0));
        for(int i=0; i<K; i++) {
            cutWire(curves[i][0], curves[i][1]);
            if(i == K-1) { // 마지막 교차점이면 S 점으로 연결
                cutWire(1, 1);
            }
        }

        double maxLen = 0;
        for(int i=1; i<wires.size()-1; i++) {
            maxLen = Math.max(wires.get(i).length, maxLen);
        }
        maxLen = Math.max(maxLen, wires.get(0).length + wires.get(wires.size()-1).length);
        System.out.println((long)maxLen); // long 형 번환 주의!!!
    }

    public static void cutWire(int x, int y) {

        Wire lastWire = wires.peek(); // 마지막으로 집어 넣은 철사 조각
        if(curX <= I && x >= I+1) { // 자르는 위치를 지나가는지 체크
            lastWire.length += (I - curX) + 0.5; // 나누어진 첫번째 조각
            Wire newWire = new Wire((x - (I+1)) + 0.5); // 나누어진 두번째 조각 생성
            wires.add(newWire);

        } else if(x <= I && curX >= I+1) {
            lastWire.length += (curX - (I+1)) + 0.5;
            Wire newWire = new Wire((I - x) + 0.5);
            wires.add(newWire);
        } else {
            lastWire.length += Math.abs(curX - x) + Math.abs(curY - y);
        }
        curX = x;
        curY = y;
    }
}