[KOI 2021] 중등부 1차 꿀 따기 문제 풀이 _ yw0515

 

 

유형 : 그리디 + dp(누적합) (dp보단 누적합에 가까운듯)

난이도 : 어렵지 않음. 그냥 30분컷

 

백준사이트꿀따기

 

KOI 사이트에 나온 풀이도 있지만 개인적인 추가 설명을 곁들여서 맛깔나게 설명해드리겠다

 

우선, 꿀의 양은 무조건 양의 정수이다.

 

얼마나 중요하면 빨간색 하이라이트에 노란색 글씨에 두껍게 썼을까?

이 양의 정수라는게 그리디적으로 매우매우 중요해진다

일단, 두벌과 벌통의 위치관계를 생각해보자

 

1. 벌통 - 벌 - 벌
2. 벌 - 벌통 - 벌
3. 벌 - 벌 - 벌통

 

위치관계는 이렇게 3가지가 있을수 있다.

1번 경우부터 살펴보자 (벌통-벌1-벌2)

벌의 순서는 왼쪽부터 매겼다

 

벌1은 벌통까지 있는것 다 먹을 수 있다

벌2는 벌통까지 있는것중, 벌1을 제외하고 다 먹을 수 있다

 

그러면, 벌1과 벌2를 고정하고 보면

 

다음과 같아서 벌통이 왼쪽 끝에 있는게 최대가 된다 (∵ a~e는 모두 양의 정수이므로)

 

그러면, 벌통의 위치는 정해졌다. 그럼 벌1은 어디에 있어야 할까? 

사실 벌1의 위치를 정하기 전에, 모두들 직감에 따라 벌2의 위치를 알고 있을것이다

 

그것은 바로 오른쪽 끝이다

 

그래야 벌1과 본인을 제외한 나머지 모든 요소를 먹을수 있다.

만약 e가 나머지 누적합을 무시할정도로 큰요소일경우가 걱정된다면, 그것은 여기서 계산이 불가능하다 (나중에 3번(벌 벌 벌통)에서 계산됨)

 

다시 돌아와, 벌1의 위치를 생각해보자. 벌2처럼 오른쪽 끝에서 2번째에 두는게 최대일까? 이 경우는 벌1이 있는 위치의 꿀의 양이(그림에서는 d) 무진장 클 경우에 성립하지 않는다. 벌2가 d를 못먹기 때문이다.

 

벌1의 위치는 위의 상황과 마찬가지로, 벌1이 있는 위치가 무진장 클 경우 때문에 해봐야 한다 => n번의 연산 필요

 

∴ 벌통은 왼쪽 끝, 벌2는 오른쪽 끝에 두고, 벌1을 그 사이에 두고 움직이며 최대를 찾으면 된다

 

2번 경우 : (벌, 벌통, 벌)

 

이렇게 될 경우, 벌과 벌 사이에 있는 요소는 모두 한번씩 먹고, 벌통에 있는걸 한번 더먹게 된다

 

일단 이걸 해봐야 하는가에 대한 논의에 대해서는, 이렇게 생각해볼수 있다

 

모든 누적합을 개무시할정도로 존나큰 개꿀이 있다고 생각해보자

 

이 개꿀이 왼쪽끝에 있을때(1번), 오른쪽 끝에 있을때(3번), 그 사이 가운데 쯤에 있을때(2번) 로 논의를 진행할수 있다. 이 개꿀이 있는 곳에 벌통을 놓아야지 2번먹음으로서 양을 최대로 불릴수 있다. 그러므로 가운데 있는걸 해봐야 하는것이다

 

그럼, 벌통 위치를 정했다면 왼쪽벌은 왼쪽끝에, 오른쪽벌은 오른쪽 끝에 두는게 언제나 최대일것이다

 

그러므로, 벌통위치만 정해주면 되는데, 위에서 말한 개꿀이 우린 정확히 어디에 위치하는지 모른다

∴벌을 양끝에 두고 벌통을 옮기며 최대를 찾아준다

 

3번 경우 : (벌, 벌, 벌통)

 

1번 경우와 좌우를 바꾼것이다

설명 안해도 되겠지?

∴ 벌통은 오른쪽 끝, 벌1는 왼쪽 끝에 두고, 벌2을 그 사이에 두고 움직이며 최대를 찾으면 된다

이렇게 그리디적 사고를 마쳤으면, 누적합으로 계산을 빠르게 할 생각을 해줘야 한다

 

누적합 1개로도 충분히 계산이 가능하겠지만, 그러기엔 귀찮으니 그냥 누적합 두개를 만들어 주었다

 

l_sum[n] = 왼쪽시작부터 n까지의 합

r_sum[n] = 오른끝부터 n까지의 합

gayggul[n] = n번째 자리에서 먹을수 있는 꿀

 

벌1 위치 : bee1

벌2 위치 : bee2

 

1번경우 : l_sum[bee1-1] + l_sum[bee2-1] - gayggul[bee1]

2번경우 : l_sum[마지막자리 -1] - gayggul[시작] + gayggul[beehive]

3번경우 : r_sum[bee1+1] + r_sum[bee2+1] - gayggul[bee2]

 

이제 코드만 짜주면 된다.

 

#include <iostream>

 

using namespace std;

 

int l_sum[100001];

int r_sum[100002];

int gayggul[100001];

 

int n;

 

int main() {

  scanf("%d", &n);

 

  for(int i = 1; i<=n; i++){

    scanf("%d", &gayggul[i]);

    l_sum[i] += l_sum[i-1];

    l_sum[i] += gayggul[i];

  }

 

  for(int i =n; i>=1; i--){

    r_sum[i] += r_sum[i+1];

    r_sum[i] += gayggul[i];

  }

  int bee1, bee2, beehive;

 

  int max_ = 0;

  // 1번경우 

  beehive = 1;

  bee2 = n;

  for(bee1 = 2; bee1<=n-1; bee1++){

    max_ = max(max_,  l_sum[bee1-1] + l_sum[bee2-1] - gayggul[bee1]);

  }

  //2번경우

  bee1 = 1;

  for(beehive = 2; beehive<=n-1; beehive++){

    max_ = max(max_,   l_sum[n -1] - gayggul[1] + gayggul[beehive]);

  }

  //3번경우

  beehive = n;

  bee1 = 1;

  for(bee2 = 2; bee2<=n-1; bee2++){

    max_ = max(max_,  r_sum[bee1+1] + r_sum[bee2+1] - gayggul[bee2]);

  }

 

  printf("%d", max_);

}

 

조금 오래걸리지만

뭐어때

시간제한 넘지 않았어

시간 복잡도는 참고로 O(3n)이다