백준 21758 꿀 따기 (2021 KOI )

 

문제링크

21758번: 꿀 따기

 

 

풀이

 

#include <stdio.h>
#include <stdlib.h>

int getMax(int a, int b){
    return a > b ? a : b;
}

int main()
{


    //init
    int answer;
    int sum = 0;
    int n;
    scanf("%d", &n);

    int arr[n];

    for(int i = 0 ; i < n; ++i){
        scanf("%d", &arr[i]);
        sum += arr[i];
    }
    sum *= 2;





    //bee1 bee2 honey //bee1 is fixed
    int b = 1;  //bee2 index
    int result = sum - arr[0]*2 - arr[b]*2;
    int temp = result;

    while(++b < n-1){   // before honey
        temp = temp + arr[b-1] - arr[b]*2;
        result = getMax(result, temp);
    }
    answer = result;



    //reverse
    b = n-2;
    result = sum - arr[n-1]*2 - arr[n-2]*2;
    temp = result;
    while(--b > 0){     // before honey
        temp = temp + arr[b+1] - arr[b]*2;
        result = getMax(result, temp);
    }
    answer = getMax(answer, result);




    //bee target bee
    //get max honey value
    int honey = 0;
    for(int i = 1; i < n-1; i++){
        honey = getMax(honey, arr[i]);
    }
    result = sum/2 - arr[0] - arr[n-1] + honey;

    answer = getMax(answer, result);




    printf("%d", answer);

    return 0;
}

 

 

---

 

 

경우는 크게 3가지 입니다.

1) 벌 벌 꿀

2) 벌     벌 꿀 //1번과 같아보이지만 벌이 연속해서 위치하지 않습니다.

3) 벌 꿀 벌

+ 1,2 번의 경우 반대의 경우도 처리해줍니다.
   (꿀이 오른쪽에 있는게 아니라, 꿀이 왼쪽인 경우)