12909 그래프 만들기

골드 상위 풀기 대작전...

이제는 플레 가고 싶어서 토요라운드에 어려운 문제 위주로 풀려고 한다.

그런데? 너무너무 어렵다

처음에는 반복문 쭉 순회만 하면 풀 수 있을 줄 알았다. 

가장 최대가 될 수 있게 노드를 붙이다가 0 0 0 10 예시에서 틀렸다는 걸 알았다. 

결국 모든 상태를 확인해야 하고 그 상태를 dp로 저장해야 겠다 싶었다. 

 

눈물의 옛날코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int degreeOfNode[55];
int maxScore[55];

int main() {
    int n;
    scanf("%d", &n);
    
    vector<int> score(n);
    for (int i = 1; i < n; i++) {
        scanf("%d", &score[i]);
    }
    
    for (int j = 2; j <= n; j++) {
        int ans = 0;
        int maxI = 0;
        for (int i = 1; i <= j - 1; i++) {
            int sum = maxScore[j - 1];
            sum -= score[degreeOfNode[i]];
            sum += score[degreeOfNode[i] + 1] + score[1];
            
            if (sum > ans) {
                ans = sum;
                maxI = i;
            }
        }
        
        degreeOfNode[maxI]++;
        degreeOfNode[j]++;
        maxScore[j] = ans;
    }
    
    printf("max: %d\n", maxScore[n]);
    
    return 0;
}

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include<cassert>
#include <climits>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()
#define MAXV 987654321

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

int score[55];
int dp[55][55];

// 노드 수, 차수
int solve(int node, int edge) {
    if (node == 1)
        return score[edge];

    int &ret = dp[node][edge];
    if (ret != -1)
        return ret;
    
    ret = 0;
    for (int i = 1; i < node; i++)
        ret = max(ret, solve(i, 1) + solve(node - i, edge + 1));
    return ret;
}

int main() {
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i < n; i++) {
        scanf("%d", &score[i]);
    }
    
    memset(dp, -1, sizeof(dp));
    
    printf("%d\n", solve(n, 0));
    
    return 0;
}