[백준/Java] 33278번 나무와 그림자 easy

-Code

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

public class BOJ33278 {
    static class Stick{
        int pos;
        long height;

        public Stick (int pos, long height) {
            this.pos = pos;
            this.height = height;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br =
                new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int stickCnt = Integer.parseInt(st.nextToken());
        long inclination = Long.parseLong(st.nextToken());

        Stick[] sticks = new Stick[stickCnt];
        for (int i = 0; i < stickCnt; i++) {
             st = new StringTokenizer(br.readLine());
            int pos = Integer.parseInt(st.nextToken());
            long len = Long.parseLong(st.nextToken());
            sticks[i] = new Stick(pos, len);
        }
        // 위치 정보를 기반으로 정렬
        Arrays.sort(sticks, Comparator.comparing(o -> o.pos));
        // 나무에 그림자 지는 길이 구하기
        long sum = 0;
        long maxShadow = Long.MIN_VALUE;
        for (int i = 0; i < stickCnt; i++) {
            Stick currStick = sticks[i];
            // 첫수는 비교할 막대기가 없으므로 이후 부터 검사
            if (i > 0) {
                // 최대 길이의 그림자의 길이가 영향 미치는지 확인
                long shadowHeight = maxShadow - (inclination * currStick.pos);
                // 최대 그림자가 해당 막대기에 그림자기 지면 추가
                if (shadowHeight > 0) {
                    sum += Math.min(currStick.height, shadowHeight);
                }
            }
            // 현재 가장큰 그림자 비교 및 저장
            long currShadow = currStick.height + inclination * currStick.pos;
            maxShadow = Math.max(maxShadow, currShadow);
        }
        System.out.println(sum);
    }
}

처음에는 현재 스틱과 다음 스틱을 가지고 n - 1번 돌면서 그림자를 비교하며 계산해 틀렸습니다.

그래서 이유를 찾아보니 예를 들면 앞에 높이가 100인 스틱이 있고 뒤에 있는 스틱들이 다 1씩으로 되어서 첫 번째 스틱이 뒤의 모든 스틱을 다 덮는 경우에 문제가 생겼습니다.

이와 같이 힌트로 현재 도달하는 최대 그림자를 저장하고 현재 위치와 기울기의 곱을 뺀 값으로 그림자의 끝 위치에서 빼주면 되므로 max값도 그냥 그림자의 끝 위치를 가지고 비교하여 저장하고 계산하면 됐습니다.

추가적으로 위치가 음수가 될수도 있어서 maxShadow의 값을 MIN_VALUE로 해야 하는데 양수만 될 줄 알고 -1로 해서 한 번 더 틀렸었습니다.