[BOJ / 백준] 백준 12841 정보대 등산 - (자바 / JAVA)

백준 12841 정보대 등산 - JAVA (자바) 

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

12841번: 정보대 등산

---

문제

백준 12841 정보대 등산

숭실 대학교 정보 과학관은 숭실 대학교 건물 중 제일 높은 곳에 있다. 민주는 평소에 버스를 타고 이 언덕을 오르지만, 이 문제에 등장하기 위하여 오늘 하루만 걸어서 올라간다.

정보 과학관을 오르는 길은 왼쪽 길과 오른쪽 길이 있다. 민주는 처음에 왼쪽 길 맨 아래에 있고 정보 과학관을 오른쪽 길 맨 위에 있다.

정보 과학관을 오르는 길은 매우 구불구불하다.

또, 길의 중간중간에는 횡단보도가 있다. 민주는 횡단보도를 한 번만 건널 수 있다.

최소한으로 걷기 위해서 민주가 건너야 하는 횡단보도의 번호와 걸어야 할 거리를 구해 더운 여름 민주를 도와주자!

 

민주가 최소 길로 가기 위해 건널 횡단보도는 몇 번째 지점에 있는지 출력하고, 민주가 최소 길로 가기 위해 걸어야 하는 거리를 출력한다.

만약, 최소 거리로 갈 수 있는 지점이 여러 곳이라면 번호가 낮은 지점을 출력한다.

 

예제 입력 :

4
2 3 1 4
1 2 3
2 5 6

---

풀이

정보대까지의 최소 거리를 구하는 문제이다.

브루트 포스와 누적합으로 풀었다.

 

• 브루트 포스 (Brute Force)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static long minValue = Long.MAX_VALUE;
    static int num = -1;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        int[] crossArr = new int[N];
        int[] leftArr = new int[N - 1];
        int[] rightArr = new int[N - 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            crossArr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N - 1; i++) {
            leftArr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N - 1; i++) {
            rightArr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 0; i < N; i++) {
            long min = crossArr[i];
            for (int left = 0; left < i; left++) {
                min += leftArr[left];
            }
            for (int right = i; right < N - 1; right++) {
                min += rightArr[right];
            }
            if (minValue > min) {
                minValue = min;
                num = i + 1;
            }
        }
        sb.append(num).append(' ').append(minValue);
        System.out.println(sb);
    }
}

 

왼쪽 길의 거리와 오른쪽 길의 거리를 leftArr와 rightArr에 각각 저장하고 횡단보도는 0번 지점부터 n - 1번까지 반복했다.

예제 입력을 기준으로

 

0번에서 건너면 오른쪽 길로 정보대까지

min = crossArr[0] + rightArr [0] + rightArr [1] + rightArr [2]

 

1번에서 건너면 왼쪽 길로 한번 나머지는 오른쪽 길

min = crossArr [1] + leftArr [0] + rightArr [1] + rightArr [2]

 

2번에서 건너면 왼쪽 길로 두 번 나머지는 오른쪽 길

min = crossArr [2] + leftArr [0] + leftArr [1] + rightArr [2]

 

3번에서 건너면 왼쪽 길로 끝까지 간 후 정보대로 건너야 함

min = crossArr [3] + leftArr [0] + leftArr [1] + leftArr [2]

 

브루트포스 알고리즘을 사용한 코드의 시간복잡도는 O(N^2)이다.

실행시간

브루트포스 사용 코드의 실행시간

 

---

• 누적 합 (Prefix Sum)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static long minValue = Long.MAX_VALUE;
    static int num = -1;

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

        int N = Integer.parseInt(br.readLine());

        int[] crossArr = new int[N];
        int[] leftArr = new int[N - 1];
        int[] rightArr = new int[N - 1];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            crossArr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N - 1; i++) {
            leftArr[i] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N - 1; i++) {
            rightArr[i] = Integer.parseInt(st.nextToken());
        }

        long[] leftPreFixArr = new long[N];
        long[] rightPreFixArr = new long[N];

        for (int i = 1; i < N; i++) {
            leftPreFixArr[i] = leftPreFixArr[i - 1] + leftArr[i - 1];
        }
        for (int i = N - 2; i >= 0; i--) {
            rightPreFixArr[i] = rightPreFixArr[i + 1] + rightArr[i];
        }

        for (int i = 0; i < N; i++) {
            long min = crossArr[i] + leftPreFixArr[i] + rightPreFixArr[i];
            if (min < minValue) {
                minValue = min;
                num = i + 1;
            }
        }

        sb.append(num).append(' ').append(minValue);
        System.out.println(sb);
    }
}

 

시간복잡도를 줄이기 위해서 누적 합 알고리즘을 사용해 보았다.

누적합은 배열의 특정 구간 합을 빠르게 계산하기 위해 사용하는 알고리즘이다.

주어진 배열에서 각 원소까지의 합을 미리 계산하여 새로운 배열에 저장한 후, 원하는 구간의 합을 빠르게 구할 수 있다.

 

브루트 포스 코드에서는 각 인덱스에 대해 반복문을 두 번 돌며 좌우의 합을 계산하고 있는데,

누적합을 사용하면 각 인덱스의 좌우 합을 미리 계산해 두고 이를 이용하여 빠르게 결과를 얻을 수 있다.

 

예제 입력을 기준으로

 

leftArr 배열

leftArr 배열

 

rightArr 배열

rightArr 배열

 

leftPreFixArr 배열

leftPreFixArr 배열

 

rightPreFixArr 배열

rightPreFixArr 배열

 

leftPreFixArr 배열은 1번 인덱스부터 N-1번 인덱스까지의 leftArr 값을 누적한 합을 저장한 배열이다.

rightPreFixArr배열은 0번 인덱스부터 N-2번 인덱스까지의 rightArr 값을 뒤에서부터 누적한 합을 저장한 배열이다.

 

누적합을 사용한 코드의 시간 복잡도는 O(N)이다.

실행시간

누적합을 사용한 코드의 실행시간

 

누적합을 사용한 코드의 실행 시간과

브루트 포스 알고리즘을 사용한 코드의 실행 시간 비교

누적합 사용 실행시간 (위), 브루트 포스 알고리즘 실행시간 (아래) 비교

 

누적합 짱짱