[백준 21758] - 꿀 따기(C++)[골드5]

문제

아래와 같이 좌우로 N개의 장소가 있다.

장소들 중 서로 다른 두 곳을 골라서 벌을 한 마리씩 둔다. 또, 다른 한 장소를 골라서 벌통을 둔다. 아래 그림에서 연한 회색의 장소는 벌이 있는 장소이고 진한 회색의 장소는 벌통이 있는 장소이다.

두 마리 벌은 벌통으로 똑바로 날아가면서 지나가는 모든 칸에서 꿀을 딴다. 각 장소에 적힌 숫자는 벌이 지나가면서 꿀을 딸 수 있는 양이다.

1. 두 마리가 모두 지나간 장소에서는 두 마리 모두 표시된 양 만큼의 꿀을 딴다. (벌통이 있는 장소에서도 같다.)
2. 벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다.

위의 그림과 같이 배치된 경우 두 마리의 벌 모두 4+1+4+9+9=27$4 + 1 + 4 + 9 + 9 = 27$의 꿀을 따서, 전체 꿀의 양은 54가 된다.

위의 그림과 같이 배치된 경우 왼쪽 장소에서 출발한 벌은 9+4+4+9+9=35$9 + 4 + 4 + 9 + 9 = 35$의 꿀을 따고 오른쪽 장소에서 출발한 벌은 4+9+9=22$4 + 9 + 9 = 22$의 꿀을 따므로, 전체 꿀의 양은 57$57$이 된다.

위의 그림과 같은 경우는 전체 꿀의 양이 31이 된다.

장소들의 꿀 양을 입력으로 받아 벌들이 딸 수 있는 가능한 최대의 꿀의 양을 계산하는 프로그램을 작성하라.

입력

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

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

출력

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

---

🔎문제 해석

벌통의 위치와 벌들의 위치에 따라 꿀의 양이 달라집니다.
우리는 이러한 벌통의 위치와 벌들의 위치를 조정해서 최대로 얻을 수 있는 꿀의 양을 구해야 합니다.
이러한 문제는 경우의 수를 무작정 전부 구하는 것보다는 최대가 나올 수 있는 경우를 특정지어서 구해주는 방법을 사용하는 것이
시간측면에서 훨씬 유리합니다.
그러기 위해서는 경우의 수를 잘 특정 지어줘야 합니다.

 

💡문제 풀이

• 벌꿀의 진행방향은 오른쪽과 왼쪽 2방향입니다.
  • 그래서 각 좌표마다 왼쪽으로 진행 시 얻을 수 있는 꿀의 양과,
    오른쪽으로 진행시 얻을 수 있는 꿀의 양을 기록했습니다.
    • 2차원배열의 형태로 honey [좌표][0] : 왼쪽합, honey [좌표][1] : 오른쪽합
• 경우의 수를 특정해서, 그 경우의 수에 해당하는 최대로 얻을 수 있는 꿀의 양을 구해줘야 합니다.
  • 경우의 수는 3가지입니다.
    1. 벌통이 왼쪽에 있는 경우
    2. 벌통이 오른쪽에 있는 경우,
    3. 벌들은 양옆 끝단에 위치하고, 벌통이 그 사이에 위치하는 경우

 

경우의 수 

1번, 2번

우선 벌통이 맨 왼쪽에 있을 경우에는 반드시 하나의 벌은 오른쪽 끝단에 위치해야 합니다.

그래야 벌이 왼쪽으로 진행하는 경우 꿀의 전체량 - (본인의 꿀+ ?위치에 벌의 꿀)이 최댓값이 됩니다.

만약 벌이 왼쪽 끝단이 아닌 경우는 꿀을 채집할 수 있는 칸 하나가 줄어들기 때문에 하나의 벌은 왼쪽 끝단으로 고정시켜야 합니다.

벌통이 오른쪽에 있는 경우도 동일합니다. 채집할 수 있는 칸의 손실을 최소로 하기 위해서 끝단에 위치해야 합니다.

 

그렇다면 나머지 벌의 위치는 어떻게 특정해야 할까요?

나머지 벌의 위치는 색칠된 영역의 합이 최대가 되는 경우입니다.

반복문을 통해서 구할 수 있습니다.

 

경우의 수 3번

벌이 양 끝단에 위치하고, 벌통이 벌들 사이에 있는 경우입니다.

해당 경우의 수는 벌통의 위치에 따라 두 벌이 채집할 수 있는 꿀의 양이 달라집니다.

이해를 쉽게 하기 위해서 왼쪽 벌을 벌 1, 오른쪽 벌을 벌 2라고 하겠습니다.

실제 벌 1의 꿀 양 : 벌1의 오른쪽합- 벌통위치에서 오른쪽합입니다.

실제 벌 2의 꿀 양 : 벌2의 왼쪽합 - 벌통위치에서 왼쪽합입니다.

이 경우는 벌통의 위치에 해당하는 꿀의 양이 젤 커야 채집하는 꿀의 양이 최대가 됩니다.

왜냐하면 벌통의 꿀은 채집할 수 있기 때문입니다.

벌통이 가운데에 위치할 경우 벌통의 꿀을 벌 1, 벌 2가 채집하기에 벌통의 꿀이 최대가 되는 경우가

경우의 수 3번이 최대의 꿀을 얻을 수 있습니다.

💻전체 코드

//백준 골드5 꿀따기
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
int n;
vector<int>graph;
vector<vector<int> >honey;
int main(){
    
    int big = 0,bidx=0,sum1,sum2,sum3=0,total=0;
    cin>>n;
    graph.resize(n,0);
    honey.resize(n,vector<int>(2,0)); //열이 0인 경우는 왼쪽합, 열이 1인 경우는 오른쪽합
    for(int i=0; i<n; i++){
        cin>>graph[i];
        total+=graph[i]; //전체 꿀의 양을 total에 저장.
    }
    int tempsum=0;
    for(int i=0; i<n; i++){
        honey[i][1]= total -tempsum-graph[i];
        honey[i][0]=tempsum;
        tempsum+=graph[i];
    }
    for(int i=1; i<n-1;i++){ //벌통이 맨 오른쪽에 있는 경우
        if(sum1<honey[0][1]+honey[i][1]-graph[i]){ //0은 오른쪽 끝단으로 고정시키고, 나머지 벌의 위치를 i로 돌려서 최대값을 찾음.
            sum1 = honey[0][1]+honey[i][1]-graph[i]; //0번 위치에서 오른쪽 합 + i위치에서 오른쪽 합 - i위치 꿀 양
        }    
    }
    for(int i= n-2; i>0; i--){ //벌통이 맨 왼쪽에 있는 경우 
        if(sum2<honey[n-1][0]+honey[i][0]-graph[i]){ //n-1은 오른쪽 끝단으로 고정시키고, 나머지 벌의 위치를 i로 돌려서 최대값을 찾음.
            sum2=honey[n-1][0]+honey[i][0]-graph[i]; //n-1 위치에서 왼쪽 합 + i 위치에서 왼쪽 합 - i 위치에 해당하는 꿀 양
        }
    }
    for(int i=1; i<n-1; i++){
        if(big<graph[i]){
            big=graph[i];
            bidx=i;
        }
    }
    sum3 = honey[0][1]-(honey[bidx][1])+honey[n-1][0]-(honey[bidx][0]); //0번 위치에서 오른쪽 합 - 벌통에서 오른쪽합 + n-1 위치에서 왼쪽합 - 벌통위치에서 왼쪽합
    int answer= max(max(sum1,sum2),sum3); //3가지 경우의 수중에서 최대값을 구합니다.
    cout<<answer;

}

 

😀느낀 점

• 최대가 되는 경우의 수를 특정지어서 문제를 푸니 훨씬 수월했다. 물론 경우의 수를 잘 특정하는 것이 관건이다!