백준 21758번 꿀 따기 (C++)

문제 링크 : https://www.acmicpc.net/problem/21758

21758번: 꿀 따기

 

이 문제는 풀이방법을 친절하게도 문제에 이미 명시를 해뒀다.

첫 번째 그림은 벌 2개가 왼쪽 끝에, 혹은 오른쪽 끝에 몰려있는 케이스를 설명하고 있으며,

두 번째 그림은 벌 하나는 왼쪽(꿀은 맨 오른쪽)이나 오른쪽 끝(꿀은 맨 왼쪽)에 고정, 다른 벌 하나는 그 사이에 존재하는 것을 설명하고 있으며,

세 번째 그림은 벌 2개가 양쪽 끝에 고정되어있고 꿀은 그 사이를 오고가는 것을 설명한다.

 

문제 풀이는 다음과 같다.

 

1. 필요한 변수를 선언하고 값을 입력받는다.

    int n = 0;
    cin >> n;
    unsigned long long ans = 0, temp = 0;
    vector<int> v(n+1,0);
    for(int i=1; i<=n; i++) cin >> v[i];

2. 다음 코드는 벌이 양쪽끝에 몰려있고 꿀은 그 반대쪽에 있는 케이스의 코드이다. 

    int i=1; // 1
    for(int j=i+1; j<=n-1; j++){ // 2
        temp = 0;
        for(int x=j+1; x<=n; x++) temp += v[x]; // 3
        for(int x=i+1; x<=n; x++){ // 4
            if(x==j) continue; 
            temp += v[x];
        }
        if(temp>ans) ans = temp; // 5
    }
    i=n; // 6
    for(int j=i-1; j>=2; j--){
        temp = 0;
        for(int x=j-1; x>=1; x--) temp += v[x];
            for(int x=i-1; x>=1; x--){
                if(x==j) continue;
                temp += v[x];
        }
        if(temp>ans) ans = temp;
    }

(1) 벌 하나가 맨 왼쪽(i=1)에 있음을 가정한다.

(2) 두 번째 벌은 i+1 부터 꿀이 존재하는 n번째 칸의 -1 사이에 존재한다.

(3) 두 번째 벌이 먹을 수 있는 꿀을 더해준다. 이때 x=j+1부터 시작하는데, 벌이 자신의 시작지점에 있는 꿀은 먹지 못하기 때문이다.

(4) 첫 번째 벌이 먹을 수 있는 꿀을 더해준다. 이때 x==j일 경우 건너뛰는데, 이유는 (3)번과 동일하다.

(5) 정답보다 현재 케이스의 꿀 합산값이 클 경우, 정답을 새로 갱신해준다.

(6) 이 경우는 꿀이 n번째가 아닌 1번째 칸에 존재하는 경우, 즉, 위의 케이스와 정 반대를 뜻한다. 구체적인 설명은 생략한다.

 

3. 다음은 양 쪽 끝에 벌이 존재하고 그 사이에 꿀이 존재하는 경우이다.

    int pos = 2; 
    while(pos<n){
        temp = 0;
        for(int i=2; i<=pos; i++) temp += v[i];
        for(int j=n-1; j>=pos; j--) temp += v[j];
        if(temp>ans) ans = temp;
        pos++;
    }

 

4. 최종적으로 정답을 출력한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n = 0;
    cin >> n;
    unsigned long long ans = 0, temp = 0;
    vector<int> v(n+1,0);
    for(int i=1; i<=n; i++) cin >> v[i];
    // 1. 벌벌 꿀
    for(int i=3; i<=n; i++) temp += v[i];
    if(temp>ans) {ans=temp; temp = 0;}
    for(int i=n-2; i>=1; i--) temp += v[i];
    if(temp>ans) {ans=temp; temp=0;}
    // 2. 벌 벌 꿀 
    int i=1;
    for(int j=i+1; j<=n-1; j++){
        temp = 0;
        for(int x=j+1; x<=n; x++) temp += v[x];
        for(int x=i+1; x<=n; x++){
            if(x==j) continue;
            temp += v[x];
        }
        if(temp>ans) ans = temp;
    }
    i=n;
    for(int j=i-1; j>=2; j--){
        temp = 0;
        for(int x=j-1; x>=1; x--) temp += v[x];
            for(int x=i-1; x>=1; x--){
                if(x==j) continue;
                temp += v[x];
        }
        if(temp>ans) ans = temp;
    }
    // 3. 벌 꿀 벌
    int pos = 2; 
    while(pos<n){
        temp = 0;
        for(int i=2; i<=pos; i++) temp += v[i];
        for(int j=n-1; j>=pos; j--) temp += v[j];
        if(temp>ans) ans = temp;
        pos++;
    }
    cout << ans << "\n";
    return 0;
}