백준 21578번 꿀 따기 (JAVA)

백준 21578번 꿀 따기 (JAVA)

문제

난이도

• 골드 5

알고리즘 분류

• 그리디 알고리즘
• 누적 합
• 많은 조건 분기

풀이

누적 합을 이용하기 위해 입력 시 누적된 합을 계산한다.

이후 중간에 벌통이 위치한 경우에서 사용하기 위해 입력 값 중 최댓값을 찾는다. (양쪽 끝 위치 제외)

벌통의 위치

1. 왼쪽 끝에 있는 경우
2. 오른쪽 끝에 있는 경우
3. 중간에 있는 경우

1. 왼쪽 끝에 있는 경우

   한 마리 벌은 오른쪽 끝에 위치 (누적 합을 최대로 만들기 위해)

   나머지 한 마리는 오른쪽 벌과 왼쪽 끝에 위치한 벌통 사이에 위치

   오른쪽 끝에 위치한 벌이 따는 꿀의 합 = (N - 2 ~ 0 까지의 합 - 나머지 벌의 위치에 있는 꿀의 값)

   중간에 위치한 벌이 따는 꿀의 합 = (현재위치 - 1 ~ 0 까지의합)

2. 오른쪽 끝에 있는 경우

   한 마리 벌은 왼쪽 끝에 위치 (누적 합을 최대로 만들기 위해)

   나머지 한 마리는 왼쪽 벌과 오른쪽 끝에 위치한 벌통 사이에 위치

   왼쪽 끝에 위치한 벌이 따는 꿀의 합 = (1 ~ N -1 까지의 합 - 나머지 벌의 위치에 있는 꿀의 값)

   중간에 위치한 벌이 따는 꿀의 합 = (현재위치 + 1 ~ N - 1 까지의합)

3. 중간에 있는 경우

   벌은 양쪽 끝에 위치하는 경우가 누적 합의 최대

   벌통이 위치하는 경우는 벌이 두 번 방문하기 때문에 벌의 위치를 제외한 나머지 위치에서 최대 값을 벌통의 위치로 한다.

   오른쪽 끝에 위치한 벌이 따는 꿀의 합 = (N - 2 ~ 벌통 위치까지의 합)

   왼쪽 끝에 위치한 벌이 따는 꿀의 합 = (1 ~ 벌통 위치까지의 합

코드

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        StringBuilder sb = new StringBuilder();

        // 타입은 long으로
        // 1. 한쪽 끝에 꿀벌, 한쪽 끝에 벌통이 위치한 경우
        // 1-2. 왼쪽 끝과 오른쪽 끝 중 통의 위치 선택
        // 2. 양쪽 끝에 꿀벌이 위치 가운데 벌통이 있는 경우, 양쪽 끝을 뺀 누적합 + 벌통의 위치 값

        // 타입은 long

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

        int[] arr = new int[N];
        long sum = 0L; // 최초 누적합

        long answer = 0L;
        int max = Integer.MIN_VALUE;

        StringTokenizer st = new StringTokenizer(in.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            sum += arr[i]; // 누적합

            if (i != 0 && i != N - 1) {
                max = Math.max(max, arr[i]);
            }
        }

        // 1. 한쪽 끝에 꿀벌, 다른 한쪽 끝에 벌통이 위치
        long first = 0L; // 자신이 위치한 곳 제외
        long calFisrt = 0L;
        long calSecond = 0L;

        // 벌통이 왼쪽 끝에 위치한 경우
        long temp1 = 0L;

        first = sum - arr[N - 1]; // N - 2 ~ 0 까지의 합

        calFisrt = first;
        calSecond = first;

        for (int i = N - 2; i >= 0; i--) {
            calSecond -= arr[i]; // 중간에 위치한 벌이 따는 꿀의 합 = (현재위치 - 1 ~ 0 까지의합)
            calFisrt = first - arr[i]; // 오른쪽 끝에 위치한 벌이 따는 꿀의 합 = (N - 2 ~ 0 까지의 합 - 나머지 벌의 위치에 있는 꿀의 값)

            if (temp1 < calFisrt + calSecond) {
                temp1 = calFisrt + calSecond;
            }
        }

        // 벌통이 오른쪽 끝에 위치한 경우
        long temp2 = 0L;
        first = sum - arr[0]; // 1 ~ N -1 까지의 합

        calFisrt = first;
        calSecond = first;

        for (int i = 1; i < N; i++) {
            calSecond -= arr[i]; // 중간에 위치한 벌이 따는 꿀의 합 = (현재위치 + 1 ~ N - 1 까지의합)
            calFisrt = first - arr[i]; // 왼쪽 끝에 위치한 벌이 따는 꿀의 합 = (1 ~ N -1 까지의 합 - 나머지 벌의 위치에 있는 꿀의 값)

            if (temp1 < calFisrt + calSecond) {
                temp1 = calFisrt + calSecond;
            }
        }

        // 2. 양쪽 끝에 꿀벌이 위치
        long temp3 = sum - (arr[0] + arr[N - 1]);   // 왼쪽 끝에 위치한 벌이 따는 꿀의 합 = (1 ~ 벌통 위치까지의 합)
                                                    // 오른쪽 끝에 위치한 벌이 따는 꿀의 합 = (N - 2 ~ 벌통 위치까지의 합)
                                                    // 즉, (1 ~ 벌통 위치 + 벌통 위치 ~ N - 2)
        temp3 += max; // 나머지중 가장 큰 값을 벌통으로, 벌통은 두 번 방문한다.

        answer = Math.max(temp1, Math.max(temp2, temp3)); // 각 경우에서 구한 값 중 최댓값

        sb.append(answer);
        out.write(sb.toString());
        out.close();
    }
}