[Java] 백준 12841 정보대 등산

[Java] 백준 12841 정보대 등산

---

문제 이해

 

1. 왼쪽 길 아래에서 시작, 오른쪽 길 위에서 끝

2. 중간에 한 번만 왼쪽에서 오른쪽으로 횡단보도 건널 수 있다.

3. 최소 거리를 구해야함 (최소 거리로 갈 수 있는 지점이 여러곳이라면 번호가 낮은 지점을 출력)

 

---

해결하기 위한 방안

 

1. Brute Force

2. 누적합

 

Brute Force로 구현하면 

 

0번 횡단보도에서 건넜을 때

total = cross[0] + right[0] + right[1] + right[2]

 

 

1번 횡단보도에서 건넜을 때

total = cross[1] + left[0] + right[1] + right[2]

 

1번 횡단보도에서 건넜을 때

total = cross[2] + left[0] + left[1] + right[2]

 

시간복잡도 O(N^2) -> 최대 100억 -> 불가능

 

누적합 구현

 

시간 복잡도 O(N)

---

풀이

 

1. 왼쪽 길의 누적합을 구함

2. 오른쪽 길의 누적합을 구함 ( 누적합을 뒤에서 부터 해야함)

3. for문으로 최소 거리를 구함

 

---

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

        // 지점 개수
        int n = Integer.parseInt(br.readLine());

        // 횡단보도 거리
        int[] cross = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            cross[i] = Integer.parseInt(st.nextToken());
        }
        // 왼쪽 길 거리
        int[] left = new int[n - 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n - 1; i++) {
            left[i] = Integer.parseInt(st.nextToken());

        }
        // 오른쪽 길 거리
        int[] right = new int[n - 1];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n - 1; i++) {
            right[i] = Integer.parseInt(st.nextToken());

        }
        // 누적합 계산
        long[] leftSum = new long[n];
        long[] rightSum = new long[n];

        for (int i = 1; i < n; i++) {
            leftSum[i] = leftSum[i - 1] + left[i - 1];
        }
        rightSum[n - 1] = 0;
        for (int i = n - 2; i >= 0; i--) {
            rightSum[i] = rightSum[i + 1]+ right[i] ;
        }
        // 최소 거리 계산
        long minDist = Long.MAX_VALUE;
        int minIdx = -1;

        for (int i = 0; i < n; i++) {
            long total = leftSum[i] + cross[i] + rightSum[i];
            if (total < minDist) {
                minDist = total;
                minIdx = i + 1;
            }
        }
        // 출력
        System.out.println(minIdx + " " + minDist);
    }

}

---

생각하지 못한 점

 

누적합을 하다보니 정수의 크기가 int의 범위를 넘어가게 되었는데 타입을 long으로 해주는 과정이 필요했다.