[BOJ/JAVA] 21758번: 꿀 따기

태그: Java

21758번: 꿀 따기

21758번: 꿀 따기

키워드

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

---

구현

• 꿀의 누적합을 구한다.

3가지 경우의 수가 생긴다.

1. 꿀통이 0에 있는 경우
   • 어처피 n-1은 못먹으므로, 하나는 무조건 한쪽 끝에 두는 것이 이득이다.
   • 나머지는 전부 돌아가며 최댓값을 찾는다.
2. 꿀통이 n-1에 있는 경우
   • 어처피 0은 못먹으므로, 하나는 무조건 한 쪽 끝에 두는 것이 이득이다.
   • 나머지는 전부 돌아가며 최댓값을 찾는다.
3. 꿀통이 중간에 있는 경우
   • 벌을 양 쪽 끝에 두는 것이 이득이다.
   • 한쪽에 2개를 두면 손해인 이유는 그 경우에 꿀통을 한쪽으로 더 밀면 더 많은 꿀을 얻을 수 있기 때문이다.

---

코드

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

public class java_21758 {
    static int N;
    static int hive[];
    static int sumOfHive[];

    static long findMaxValue(int hiveIndex) {
        long result = 0;

        // 한 쪽 끝에 있는 경우
        if (hiveIndex == 0) {
            // 하나는 n-1에 고정
            for (int i = 1; i < N - 1; i++) {
                // n-1 합 저장
                long tmp = sumOfHive[N - 2] - hive[i];

                tmp += sumOfHive[i - 1];

                result = Math.max(result, tmp);
            }

            return result;
        }

        // 한 쪽 끝에 있는 경우
        if (hiveIndex == N - 1) {
            // 하나는 0에 고정
            for (int i = 1; i < N - 1; i++) {
                // [1]~[N-1] 합 저장
                long tmp = sumOfHive[N - 1] - hive[0] - hive[i];

                tmp += sumOfHive[N - 1] - sumOfHive[i];

                result = Math.max(result, tmp);
            }

            return result;
        }

        // 중간에 있는 경우
        // 양쪽 끝에 벌을 둔다.
        // [1]~[hiveIndex]
        // [hiveIndex]~[n-2]
        result += sumOfHive[hiveIndex] - sumOfHive[0];
        result += sumOfHive[N - 2] - sumOfHive[hiveIndex - 1];

        return result;
    }

    static long solution() {
        long result = 0;

        // 벌통의 위치
        for (int i = 0; i < N; i++) {
            result = Math.max(findMaxValue(i), result);
        }

        return result;
    }

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

        // 벌통이 한쪽 끝에 있는 경우
        // -> 하나는 무조건 다른 한 쪽 끝 (다른 한 쪽 끝이 MAX값이여도 어처피 못먹음)
        // -> N번 반복해서 최댓값 찾기

        // 벌통이 중간에 있는 경우
        // -> 한쪽 끝에 2개를 두는 것이 이득인가?
        // --> [2]부터 [벌통] 까지 합 * 2
        // -> 양쪽 끝에 2개를 두는 것이 이득인가?
        // --> [1]부터 [벌통] 까지 합 + [벌통]부터 [n-2] 까지 합

        N = Integer.parseInt(br.readLine());
        hive = new int[N];
        sumOfHive = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        hive[0] = Integer.parseInt(st.nextToken());
        sumOfHive[0] = hive[0];

        for (int i = 1; i < N; i++) {
            hive[i] = Integer.parseInt(st.nextToken());
            sumOfHive[i] = sumOfHive[i - 1] + hive[i];
        }

        long result = solution();

        System.out.println(result);

        br.close();
    }
}

---