[백준 12841] 정보대 등산 [Java]

문제

https://boj.ma/12841

12841번: 정보대 등산

 

---

풀이

왼쪽의 1번부터 오른쪽 N번까지 횡단보도를 하나만 건너서 갈 때 최소 거리를 구하는 문제다.

횡단보도를 제외한 나머지 구간의 합을 매번 구하면 시간초과가 발생한다.

누적합을 미리 계산해 주자.

최대 거리가 10만인 10만 개의 구간의 주어진다. long을 사용하자.

        // Solve
        long[] prefixSumL = new long[N];
        long[] prefixSumR = new long[N];
        for (int i = 1; i < N; ++i) {
            prefixSumL[i] = prefixSumL[i - 1] + L[i - 1];
            prefixSumR[i] = prefixSumR[i - 1] + R[i - 1];
        }

첫 번째 횡단보도부터 시작해서 N번째 횡단보도까지 하나씩 건너보자.

총 거리는 횡단보도를 건너기 전 왼쪽 구간의 합 + 횡단보도 길이 + 횡단보도를 건넌 후 오른쪽 구간의 합이다. 최소 거리가 여러 개라면 번호가 낮은 지점을 출력하므로 조건 분기 내에서 인덱스를 기록해주자.

        long res = Long.MAX_VALUE, idx = -1;
        for (int i = 0; i < N; ++i) {
            final long temp = prefixSumL[i] + A[i] + (prefixSumR[N - 1] - prefixSumR[i]);
            if (temp < res) {
                res = temp;
                idx = i;
            }
        }

풀이 시간

8분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/12841.java

problem-solving/baekjoon-online-judge/easy/12841.java at main · rogi-rogi/problem-solving