백준 2228번 구간 나누기

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

인덱스, 구간의 수, 선택을 통해 메모이제이션하는 발상은 쉽게 떠올랐지만 구현하는데 애를 먹었던 문제였습니다.

항상 기저사례를 먼저 작성한 뒤 조건 만족하는 경우를 고려했었는데 해당 문제는 조건 만족하는 경우를 먼저 고려해야지만 AC를 받을 수 있는 문제였습니다.

알고리즘 자체는 간단합니다.

1. select==false 즉, 새로운 구간을 찾을 때는 해당 인덱스를 건너 뛰거나 해당 인덱스부터 새로운 구간이 시작됩니다.

2. select==true 일 때는, 기존 구간을 끝내거나 해당 인덱스를 추가하는 경우가 있습니다.

3. 구간의 수가 M이거나 구간의 수가 M-1이고 select==true일 때는 조건을 충족하고 그 외의 경우는 모두 고려하지 않습니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MININF = -987654321;

const int MAX = 100;

int N, M;

int arr[MAX];

int cache[MAX][MAX / 2][2]; //N, M, 구간에 포함(Yes/No)

 

//캐쉬 초기화(음수는 memset 적용 불가

void initialize(void)

{

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

                 for (int j = 0; j < M; j++)

                         for (int k = 0; k<2; k++)

                                 cache[i][j][k] = MININF;

}

 

int rangeMaxSum(int idx, int rangeNum, bool select)

{

        //조건 충족

        if (rangeNum == M)

                 return 0;

        //기저 사례

        if (idx == N)

        {

                 //마지막 구간을 고르면 조건 충족

                 if (rangeNum == M - 1 && select)

                         return 0;

                 //그 외에는 조건 충족 못함

                 else

                         return -32768 * 100; //최솟값 * N의 최대

        }

 

        int &result = cache[idx][rangeNum][select];

        if (result != MININF)

                 return result;

 

        //새로운 구간

        if (!select)

                 //그냥 지나치기 vs idx부터 시작하기

                 return result = max(rangeMaxSum(idx + 1, rangeNum, false), arr[idx] + rangeMaxSum(idx + 1, rangeNum, true));

        //기존 구간

        else

                 //구간 끝내기 vs 기존 구간에 추가하기

                 return result = max(rangeMaxSum(idx + 1, rangeNum + 1, false), arr[idx] + rangeMaxSum(idx + 1, rangeNum, true));

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 속도 향상

        cin >> N >> M;

 

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

                 cin >> arr[i];

 

        initialize();

 

        cout << rangeMaxSum(0, 0, false) << endl;

        return 0;

}

 

개발환경:Visual Studio 2017

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