[백준 - 21758][Gold 5] - 꿀 따기 (JAVA)

문제 링크

---

 

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

 

문제

---

 

입력

---

첫 번째 줄에 장소의 수 N이 주어진다.

다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.

 

출력

---

첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.

 

구현으로 풀릴까??

---

우선 가장 쉬운 방법인 구현을 생각해보자. 

벌통의 위치 1개와 꿀벌의 위치 2개를 선정해서 꿀의 합을 구하는 코드를 만들면 조합이기 때문에 다음과 같은 시간복잡도가 나온다.

 

O(N)
= (벌통 위치 고르기) + (꿀벌 1 위치 고르기) + (꿀벌 2 위치 고르기)
= (N*(N-1)*(N-2))/(3*2*1)
≒ N^3

 

N의 최대값이 100,000이기 때문에 최대 연산 횟수가 1,000,000,000,000,000이다. 이는 1억보다 훨신 큰 숫자이기 때문에 원하는 시간인 1초 이내로 해결할 수 없다. 다른 방법을 찾아보자.

 

누적합의 값을 최대로 얻으려면 어떻게 해야할까?? with 그리디

---

벌통과 꿀벌의 사이의 꿀을 모두 꿀벌의 위치를 제외하고 모두 더하는 것이기 때문에 누적합 문제로 보인다. 누적합의 값을 가장 크게 얻으려면 가장 많이 더하면 되므로 벌통과 꿀벌의 위치를 가장 길게 잡으면 최대값을 얻을 수 있지 않을까??

벌통과 꿀벌의 위치를 길게 잡기 위해선 다음과 같은 방법이 있다.

• 벌통을 가장 왼쪽에 두고 나머지 벌을 오른쪽 끝에 두기
• 벌통을 가장 오른쪽에 두고 나머지 벌을 왼쪽 끝에 두기
• 벌을 양쪽 끝에 두고 벌통을 벌 사이에 두기

 

이렇게 둔다면 가장 벌통과 꿀벌사이의 거리를 길게 잡을 수 있으므로 큰 값을 얻을 수 있을 것 같다!

 

하지만 아래와 같은 반례가 있다.

 

1(벌통)

1

1

9(꿀벌)

1(꿀벌)

 

위의 예시를 보면 꿀벌의 위치는 벌꿀을 먹을 수 없기 때문에 위의 방법으로 꿀을 얻으면 1+1+1+1+1+1 = 6이다. 하지만 아래를 보자.

 

1(벌통)

1

1 (꿀벌)

9

1(꿀벌)

 

위의 방법으로 꿀을 얻으면 1+1+1+1+9 = 13이다! 그러므로 꿀벌 1마리와 벌통 1개를 양 끝에 두고 사이에 꿀벌의 위치를 조종하면서 최대값을 구해야할 필요가 있다.

 

그리디의 시간복잡도를 계산해보자

---

위의 3가지 방법으로 구현하면 시간복잡도는 다음과 같다.

 

O(N)
= (벌통 왼쪽, 꿀벌 1 오른쪽에 두고 가운데 꿀벌 옮기기) + (벌통 오른쪽, 꿀벌 1 왼쪽에 두고 가운데 꿀벌 옮기기) + (꿀벌을 양쪽에 두고 가운데 벌통 옮기기)
= N + N + N
≒ N

 

N의 최대값이 100,000이기 때문에 최대 연산 횟수가 100,000이다. 이는 1억보다 작은 연산 횟수이기 때문에 1초 이내에 해결할 수 있다!

 

문제 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        long[] honeySum = new long[N+1];
        long[] honeys = new long[N+1];
        long[] input = Arrays.stream(br.readLine().split(" ")).mapToLong(Long::parseLong).toArray();
	
    	//누적합 구하기
        for(int i=0;i<input.length;i++){
            honeys[i+1] = input[i];
            honeySum[i+1] = honeySum[i] + input[i];
        }

        long max = 0L; //최대 꿀양

        //벌통이 오른쪽 끝에 있는 경우
        long leftHoneySum = honeySum[N] - honeys[1];

        for(int i=2;i<honeys.length-1;i++){
            long midHoneySum = honeySum[N] - honeySum[i];
            long sum = leftHoneySum - honeys[i] + midHoneySum;
            max = Math.max(sum,max);
        }

        //벌통이 왼쪽 끝에 있는 경우
        long rightHoneySum = honeySum[N-1];

        for(int i=honeys.length-2;i>0;i--){
            long midHoneySum = honeySum[i-1];
            long sum = rightHoneySum - honeys[i] + midHoneySum;
            max = Math.max(sum,max);
        }


        //벌통이 가운데 있는 경우
        for(int i=1;i<honeys.length-1;i++){
            long sum = honeySum[i] - honeySum[1] + honeySum[N-1] - honeySum[i-1];
            max = Math.max(sum,max);
        }

        System.out.println(max);
    }
}

 

 

실행 결과

---

 

 

제한시간인 1초 안에 문제가 해결되었다!

 

키워드

---

• 최대값
  • 완전탐색, DP, 그리디의 가능성이 있다.
• N = 100,000
  • 선형탐색, 정렬의 가능성이 있다.

 

팁

---

• 누적합은 길이가 길면 큰 값을 얻을 확률이 높다.