[백준] 꿀 따기 : 21758 : JAVA

1.  🍅 문제

21758번: 꿀 따기

 

 

---

 

 

2.  🤔 어떻게 풀까?

구해야 되는 것 : 얻을 수 있는 최대 꿀의 양

조건 : 벌 2마리가 지나가면 꿀을 채취할 수 있음, 단 벌이 시작한 위치에서는 어느 벌이든 채취하지 못함

 

조건 속에서 최대 꿀의 양을 구하기 위해 가능한 루트를 생각했다. 생각할 수 있는 루트는 3가지이다. 

1. 벌 2마리가 같이 왼쪽에서 오른쪽으로 전진

2. 벌 2마리가 같이 오른쪽에서 왼쪽으로 전진

3. 벌 2마리가 양 끝에서 전진

 

이 3가지의 상황을 모두 따져가면서 해보면 최대 꿀의 양을 찾을 있지 않을까? ..하지만 경우의 수를 다 해보면 시간 초과가 날 것 같아서 더 좋은 방법이 없을까 고민하였다. 결국 찾을 수 없어서 다시 생각해봤는데 입력의 최대가 100,000이라서 O(n)으로 구현할 수 있으면 시간초과가 안난다! 근데 의문은 마지막 서브태스크의 조건이 '제한 없음'이라는 것이 N이 100,000이하를 가리키는 것일까? 아마 그런 것 같다.

 

 

3 .  💡 로직

O(n)으로 구현하기 위한 핵심은 한 번 루프를 돌 때 구간 합과 손실 꿀의 양을 구해는 것이다. 구간합은 말 그대로 현재 위치까지 누적된 꿀의 양이고, 손실 꿀의 양은 해당 위치에 벌을 배치할 시 잃게 되는 꿀의 양이다. 우리는 손실 꿀양이 가장 적은 곳에 벌을 배치하면 된다.

 

문제의 특성상 첫 번째 벌은 무조건 처음 위치에서 시작할 때 가장 베스트이다. 왜냐하면 벌이 지나가기만 하면 꿀을 얻기 때문이다. 그래서 생각해야 되는 것은 '두 번째 벌을 어디에 배치하는 것이냐'이다. 

 

위치에 따라 전체 손실되는 꿀의 양을 생각 해봤을 때, 만약 두 번째 벌의 위치를 3이라고 하자. 그럼 0~3(자기 위치 포함) 위치에 있는 꿀은 얻을 수 없다. 또한 첫 번째 벌이 지나가면서 위치 3의 꿀을 얻을 수 없다. 그러므로 손실 꿀의 양은 `honeySum[i] + honey[i]`이다. 모든 장소에서 손실 꿀의 양을 구한 다음 가장 적은 손실 꿀의 양을 선택한다.

lossHoney = honeySum[i] + honey[i]

이제 얻을 수 있는 꿀의 양을 구하기만 하면 된다. 바로 2개의 전체 꿀의 양에서 손실 꿀을 빼주면 된다.

honeySum[N-1]*2 - lossHoney;

다음과 같이 3가지 상황에 따라 얻을 수 있는 최대 꿀을 알아내고 그 중 가장 큰 값을 고른다.

  public void solution(){
        //1. 벌들이 같은 방향
        //1.1 벌이 오른쪽 -> 왼쪽으로 향할 때
        long result = getHoneyLeftToRight();
        maxHoneyAmount = Math.max(result, maxHoneyAmount);

        //1.2 벌이 왼쪽 -> 오른쪽으로 향할 때
        result = getHoneyRightToLeft();
        maxHoneyAmount = Math.max(result, maxHoneyAmount);

        //2. 벌들이 양옆에서 올 때
        result = getHoneyCenter();
        maxHoneyAmount = Math.max(result, maxHoneyAmount);
    }
    
    
 public long getHoneyLeftToRight(){
        long honeySum [] = new long[N];
        long lossHoney = Integer.MAX_VALUE;

        for(int i=1; i<N; i++){
            honeySum[i] = honeySum[i-1] + honey[i];
            if(lossHoney > honeySum[i] + honey[i]){
                lossHoney = honeySum[i] + honey[i];
            }
        }

        return honeySum[N-1]*2 - lossHoney;
    }

 

 

4 .  🖥️  전체 코드

import java.io.*;
import java.util.StringTokenizer;

public class Main{

    BufferedReader br;
    BufferedWriter bw;

    static int N;
    static int honey [];
    long maxHoneyAmount;

    public Main(){
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        maxHoneyAmount = 0;
    }

    public void run() throws IOException {
        input();
        solution();
        output();
    }

    public void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        honey = new int[N];
        StringTokenizer st= new StringTokenizer(br.readLine());

        // 장소마다 꿀의 양 입력받음
        for(int i=0; i<N; i++){
            honey[i] = Integer.parseInt(st.nextToken());
        }
    }

    public void solution(){
        //1. 벌들이 같은 방향
        //1.1 벌이 오른쪽 -> 왼쪽으로 향할 때
        long result = getHoneyLeftToRight();
        maxHoneyAmount = Math.max(result, maxHoneyAmount);

        //1.2 벌이 왼쪽 -> 오른쪽으로 향할 때
        result = getHoneyRightToLeft();
        maxHoneyAmount = Math.max(result, maxHoneyAmount);

        //2. 벌들이 양옆에서 올 때
        result = getHoneyCenter();
        maxHoneyAmount = Math.max(result, maxHoneyAmount);
    }

    public void output() throws IOException {
        bw.write(maxHoneyAmount +"\n");
        bw.flush();

        bw.close();
        br.close();
    }

    public long getHoneyLeftToRight(){
        long honeySum [] = new long[N];
        long lossHoney = Integer.MAX_VALUE;

        for(int i=1; i<N; i++){
            honeySum[i] = honeySum[i-1] + honey[i];
            if(lossHoney > honeySum[i] + honey[i]){
                lossHoney = honeySum[i] + honey[i];
            }
        }

        return honeySum[N-1]*2 - lossHoney;
    }

    public long getHoneyRightToLeft(){
        long honeySum [] = new long[N];
        long lossHoney = Integer.MAX_VALUE;

        for(int i=N-2; i>=0; i--){
            honeySum[i] = honeySum[i+1] + honey[i];
            if(lossHoney > honeySum[i] + honey[i]){
                lossHoney = honeySum[i] + honey[i];
            }
        }
        return honeySum[0]*2 - lossHoney;
    }

    public long getHoneyCenter(){
        long honeySum = 0;
        long maxHoney = 0;

        for(int i=1; i<N-1; i++){
            honeySum += honey[i];
            if(maxHoney < honey[i]){
                maxHoney = honey[i];
            }
        }

        return honeySum + maxHoney;
    }

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

        new Main().run();

    }



}