백준 2229번 조 짜기

문제 링크입니다: https://www.acmicpc.net/problem/2229

한명으로 구성된 조도 있다는 것을 고려해준다면 어렵지 않은 DP 문제였습니다.

알고리즘은 아래와 같습니다.

1. 조를 나누는데 1 ~ (N - idx)명까지 나눕니다.

2. 해당 조의 최대 점수와 최소 점수 차를 더해가며 메모이제이션을 하면 됩니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000;

const int INF = 987654321;

 

int N, result;

int arr[MAX];

int cache[MAX]; //idx

 

int maxDifference(int idx)

{

        //기저 사례: 범위 초과

        if (idx == N)

                 return 0;

 

        int &result = cache[idx];

        if (result != -1)

                 return result;

 

        result = 0;

        int low = INF, high = -1;

        //조를 나눈다(한명으로 구성된 조도 있다)

        for (int i = idx; i < N; i++)

        {

                 low = min(low, arr[i]);

                 high = max(high, arr[i]);

 

                 result = max(result, (high - low) + maxDifference(i + 1));

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도

        cin >> N;

 

        for (int i = 0; i < N; i++)

                 cin >> arr[i];

 

        memset(cache, -1, sizeof(cache));

        cout << maxDifference(0) << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~