[SWEA] 9780 외계인 침공

출처: SWEA

 Input 

2

2

10 20

6

5 9 1 3 7 2

 

 Output 

#1 20

#2 16

 

DP 관점에서 문제를 해결할 수 있습니다. (부분문제 해결)

ex) 도시 = [1 2 3 4 5]가 있을 때, (도시에 사는 개구리 수와 상관없이) 많은 도시를 침공할 수 있는 경우?

1 → 3 → 5를 차례로 공격하는 경우입니다. 

문제 규칙에 따르면 침공한 도시의 양옆은 납치할 수 있는 개구리가 없습니다.

결국, 도시에 사는 개구리 수에 따라 도시를 공격할 지, 아니면 다른 도시를 공격할 지 결정해야 합니다.

 

▶ DP[i] = max(DP[i - 2] + A[i], DP[i - 1])

    : i번째 도시까지 침공했을 때 납치할 수 있는 개구리의 최대값

 

도시가 1개인 경우, 개구리 수와 상관없이 침공.

→ DP[1] = A[1]

도시가 2개인 경우, 첫번째와 두번째 도시 중 더 많은 개구리가 있는 도시를 선택해야 합니다.

→ DP[2] = max(A[1], A[2])

도시가 3개인 경우, [1] + [3] 혹은 [2]로 나눌 수 있습니다.

→ DP[3] = max(DP[1] + A[3], DP[2])

도시가 4개인 경우, 

→ DP[4] = max(DP[2] + A[4], DP[3])

---

#include <iostream>
#define max(a, b) (a > b ? a : b)
using namespace std;
const int MAX = 1000000;
int N, A[MAX + 1];
long long DP[MAX + 1];
 
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    
    int testCase; cin >> testCase;
    for (int tc = 1; tc <= testCase; ++tc) {
        cin >> N;
        for (int i = 1; i <= N; i++)
            cin >> A[i]; 
        
        DP[1] = A[1];
        DP[2] = max(A[1], A[2]);
        for (int i = 3; i <= N; i++){
            DP[i] = max(DP[i - 2] + A[i], DP[i - 1]);
        }
        
        cout << "#" << tc << " ";
        cout << DP[N] << '\n';
    }
}