[백준] 21758 꿀 따기 - Java

 

 

 

문제 출저

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

21758번: 꿀 따기

 

 

 

문제 풀이

꿀의 정보가 주어집니다. 꿀벌 2개와 벌통을 위치합니다. 꿀벌은 자신의 위치에서 벌통까지 경로에 있는 모든 꿀을 채집합니다. (벌통의 꿀도 포함합니다. 다만, 꿀벌이 있는 위치는 가져오지 못 합니다.) 이때 채집할 수 있는 꿀의 최대 크기를 구하는게 이 문제의 요구사항 입니다.

 

 

누적합으로 풀었습니다. 

왼쪽에서 시작해 합을 누적하는 배열, 오른쪽에서 시작해 합을 누적하는 배열, 총 2개를 만들었습니다.

 

 

3가지 경우를 두었습니다.

벌통(맨 왠쪽), 꿀벌1, 꿀벌2(맨 오른쪽)

꿀벌1, 벌통, 꿀벌2

꿀벌1, 꿀벌2, 벌통

 

최대한 많은 꿀을 채집해야 하므로 양 끝에 오브젝트를 배치하고 가운데 위치를 조정하여 값을 구했습니다.

 

맨 처음 3가지 위치를 3중 for문으로 나타냈는데 시간 초과가 발생한 거 같습니다. N의 최댓값이 100,000 이므로

100,000의 3제곱은 백만을 넘기 때문입니다.

 

 

 

소스 코드

package baekjoon.backjoon10.day0110.day04;

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


/*
꿀 따기
https://www.acmicpc.net/problem/21758

누적합
3가지 경우로 나누어서 계산
꿀통 벌1 벌2
벌1 꿀통 벌2
벌1 벌2 꿀통
가운데가 위치를 이동

 */
public class B21758 {

    static int n;
    static long[] board;
    static long[] leftPrefix; // 왼쪽부터 시작
    static long[] rightPrefix; // 오른쪽부터 시작

    static int beeHouse;
    static int beeOne;
    static int beeTwo;

    static long answer;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        board = new long[n];
        for(int i = 0; i < n; i++) {
            board[i] = Long.parseLong(st.nextToken());
        }

        leftPrefix = new long[n];
        long prefer = 0;
        for(int i = 0; i < n; i++) {
            leftPrefix[i] = board[i] + prefer;
            prefer = leftPrefix[i];
        }

        rightPrefix = new long[n];
        prefer = 0;
        for(int i = n-1; i >= 0; i--) {
            rightPrefix[i] = board[i] + prefer;
            prefer = rightPrefix[i];
        }

        answer = 0;

        // 벌통, 벌2, 벌1
        left();

        // 벌1, 벌통, 벌2
        center();

        // 벌1, 벌2, 벌통
        right();

        System.out.println(answer);

    }

    // 벌통 왼쪽, 벌1 맨 오른쪽, 벌2 움직임
    public static void left() {
        beeHouse = 0;
        beeOne = n-1;

        for(int i = 1; i < n-1; i++) {
            beeTwo = i;
            long result = rightPrefix[beeHouse] - rightPrefix[beeOne];
            result += rightPrefix[beeHouse] - rightPrefix[beeTwo];
            result -= board[beeTwo];
            answer = Math.max(answer, result);
        }

    }

    // 벌1 왼쪽, 벌통, 벌2 오른쪽
    public static void center() {
        beeOne = 0;
        beeTwo = n-1;

        for(int i = 1; i < n-1; i++) {
            beeHouse = i;
            long result = 0;
            result += leftPrefix[beeHouse] - leftPrefix[beeOne];
            result += rightPrefix[beeHouse] - rightPrefix[beeTwo];
            answer = Math.max(answer, result);
        }

    }

    // 벌1, 벌2, 벌통
    public static void right() {
        beeOne = 0;
        beeHouse = n-1;

        for(int i = 1; i < n-1; i++) {
            beeTwo = i;
            long result = leftPrefix[beeHouse] - leftPrefix[beeOne];
            result += leftPrefix[beeHouse] - leftPrefix[beeTwo];
            result -= board[beeTwo];
            answer = Math.max(answer, result);
        }
    }
}

 

 

 

 

참조 사이트

https://hy-ung.tistory.com/64

백준 21758번 - 꿀 따기