[백준] 2229번 조 짜기

[적용한 알고리즘]

DP

[아이디어]

앞선 게시물 기지국과 거의 같은 방식으로 접근했다. 

구획을 연속적으로 진행하므로, 

dp[i] = max(dp[j - 1] + (i ~ j 까지 조 짜기 점수)) 로 해줬다. 

 

[생각의 흐름 / 절차] 

 

[교훈]

DP는 풀수록 모르겠다ㅋㅋ

 

<코드>

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

int dp[1001];
int main(){
    int N;
    scanf("%d", &N);

    vector<int> score(N + 1);
    for (int i = 1; i <= N; i++){
        scanf("%d", &score[i]);
    }

    for (int i = 1; i <= N; i++){
        int Max = -1;
        int Min = 10001;

        for (int j = i; j >= 1; j--){
            Max = max(score[j], Max);
            Min = min(score[j], Min);

            int res = Max - Min;

            dp[i] = max(dp[j - 1] + res, dp[i]);
        }
    }

    printf("%d\n", dp[N]);
    return 0;
}