[TopCoder] BadNeighbors (나쁜 이웃들)

옛 노래는 "이웃을 미워하라"고 선언하고, 오네틴빌 주민들은 그 말을 마음에 새겼다. 모든 주민들은 양쪽 모두 옆집 이웃들을 싫어한다. 그의 이웃들만큼 마을 우물에서 멀리 떨어진 곳에 살고 싶어하는 사람은 아무도 없기 때문에 마을은 우물 주위에 큰 원을 그리며 배열되어 있다. 불행하게도, 그 마을의 우물은 황폐해졌고 복구가 필요하다. 당신은 세이브 오어 웰 기금을 위한 기부금을 모으기 위해 고용되었습니다.

마을 주민 각자는 기부금에 명시된 대로 일정 금액을 기부할 의사가 있으며, 이는 우물 주위에 시계 방향으로 나열되어 있다. 하지만, 아무도 그의 이웃이 기부한 기금에 기꺼이 기부하려 하지 않는다. 기부금의 첫 번째와 마지막 항목이 이웃을 위한 것이라는 점을 제외하고는 이웃이 기부금에 항상 연속적으로 등재된다. 모금할 수 있는 기부금의 최대 금액을 계산하여 반환해야 합니다.

Definition

Class:

 

BadNeighbors

Method:

 

maxDonations

Parameters:

 

vector <int>

Returns:

 

int

Method signature:

 

int maxDonations(vector <int> donations)

(be sure your method is public)

Examples

0)

{ 10, 3, 2, 5, 7, 8 }

Returns: 19

The maximum donation is 19, achieved by 10+2+7. It would be better to take 10+5+8 except that the 10 and 8 donations are from neighbors.

1)

{ 11, 15 }

Returns: 15

2)

{ 7, 7, 7, 7, 7, 7, 7 }

Returns: 21

3)

{ 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }

Returns: 16

4)

{ 94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237, 12, 72, 74, 29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45, 435, 7, 36, 57, 86, 81, 72 }

Returns: 2926

 

---

일직선 배열에서 배낭 문제처럼 배열에서 요소들의 합을 구해 가장 큰 sum을 return하는 문제이다. 

 

제약 조건으로서 배열의 이웃한 요소들은 연달아서 선택할 수 없다. 

 

{ 10, 3, 2, 5, 7, 8 }

 

또한 원형의 형상을 가정하고 있기 때문에 가장 첫번째 요소와 마지막 요소를 서로 이웃한 것으로 간주한다. 

 

순회를 하되, 불필요한 탐색을 피하기 위해 동적 계획법을 사용하였다.

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

class BadNeighbors{
    public:
    int maxDonations(vector<int> donations){
        if(donations.size()==2){
            return max(donations[0], donations[1]);
        }

먼저 전체 배열의 길이가 2인 경우 가장 단순하게 더 큰 기부금을 내는 요소를 선택한다. 

 

        int N = donations.size();
        int *dp = new int[N];
        
        int donation1 = getTotalDonation(dp, donations, 0, N-1);
        int donation2 = getTotalDonation(dp, donations, 1, N);
        
        return max(donation1, donation2);
    }

배열 길이가 3이상인 경우, 누적 기부금액을 추적하기 위한 dp 배열을 선언한다. 

 

첫번째 요소부터 마지막에서 두번째 요소까지 고려한 결과와

 

두번째 요소부터 마지막 요소까지 고려한 결과를 서로 비교하여 더 큰 값을 반환함으로써 최대 기부금액합을 구한다.

    int getTotalDonation(int *dp, vector<int> donations, int start, int end){
        int ans = 0;
        for(int i=start; i<end; i++){
            dp[i] = donations[i];
            if(i > start)
            {
                dp[i] = max(dp[i-1], dp[i]);
                if(i > start+1){
                    dp[i] = max(dp[i], dp[i-2] + donations[i]);
                }
                ans = max(ans, dp[i]);
            }
        }
        return ans;
    }

배열에서 최대 누적 기부금액을 구하는 함수이다. 

            dp[i] = donations[i];

먼저 i번째 요소를 i번째 집에서 기부하는 금액으로 초기화해준다. 

            if(i > start)
            {
                dp[i] = max(dp[i-1], dp[i]);

그리고 두번째 요소에 진입한 시점부터는 이전 집까지의 누적기부금액과 나(i)의 기부금액을 비교한다. 

 

나의 기부금액이 더 클 경우, 이전 누적 기부금액을 고려할 필요 없이 나의 기부금액(donation[i])으로 설정한다. 

 

그게 아니라면 나의 기부금액은 무시하고 이전 누적 기부금액(dp[i-1])으로 설정한다.

 

                if(i > start+1){
                    dp[i] = max(dp[i], dp[i-2] + donations[i]);
                }
                ans = max(ans, dp[i]);

세번째 요소부터는 이렇게 구해진 누적 기부금액(dp[i-1] 혹은 donation[i])과 전전 누적기부금액(dp[i-2])과 나의 기부금액

 

비교하여 저장한다. 

 

전체 for문을 순회하고 나면 배열의 최종 최대 누적기부금액이 구해진다.