백준 1744: 수 묶기 [C/C++], 다이나믹 프로그래밍

https://www.acmicpc.net/problem/1744

1744번: 수 묶기

 

#include <iostream>
#include <vector>
#include <algorithm>
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int N;
vector<int> lis;
vector<int> dp;
void input();
long long dfs(int i, int val);
int main() {
    fastio();
    input(); 
    cout << dfs(0, 0);
    return 0;
}
void input() {
    cin >> N;
    lis = vector<int>(N);
    dp = vector<int>(N + 1);
    for (int i = 0; i < N; i++) cin >> lis[i];
    sort(lis.begin(), lis.end(), greater<>());
}
long long dfs(int i, int val) {
    if (i == N) return val;
    else if (i == N - 1) return val + lis[i];
    else {
        if (dp[i]) return dp[i] + val;
        else {
            dp[i] = max(dfs(i + 1, val + lis[i]), 
                        dfs(i + 2, val + lis[i] * lis[i + 1])) - val;
            return dp[i] + val;
        }
    }
}
 

다이나믹 프로그래밍입니다.

 

풀이:

 

1. 큰 수끼리 더하는 것 보다 곱하면, 큰 수가 나올 확률이 높습니다.

그렇지만 가장 큰 수 두개가 100, -1 일 경우 곱하면 -100이 나옵니다.

그래서 반드시 그리디 하게 곱하면 안된다는 것이 명확합니다.

 

2. 모든 경우의 수를 구합니다. 

하지만 브루트 포스의 경우 O(2^n)의 시간 복잡도라 시간 초과가 됩니다. 

 

3. 다이나믹 프로그래밍을 사용합니다.

이미 구한 답을 사용하여 시간복잡도를 극적으로 상승 시킵니다.