[Algorithm]Baekjoon 2228번 :: 구간 나누기

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, m;
int arr[101] = { 0 };
int dp[101][101] = { 0 };
const int minNum = -40000000;
 
int DFS(int index, int createCount)
{
    if (createCount > m) return 0; // 더이상 포함시킬 게 없다.
    if (index > n) return minNum; // 비교자체(38번째 라인)를 무효화한다. 반드시 m개만큼의 구간을 만들어야하기 때문.
    
    int& result = dp[index][createCount];
    if (result != -1) return result;
 
    result = DFS(index + 1, createCount); // 이번 수를 아예 제외시키기.
    int sum = 0;
 
    for (int i = index; i <= n; ++i)
    {
        sum += arr[i];
        result = max(result, sum + DFS(i + 2, createCount + 1));
    }
 
    return result;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> arr[i];
    }
 
    memset(dp, -1, sizeof(dp));
 
    cout << DFS(1, 1);
}

쉽지 않았던 문제이다.

dp테이블은 dp[i][j] == 1~i번쨰까지 숫자들을 j개의 그룹으로 나눴을 때의 최대합이다.

그리고 각 그룹은 '인접하지 않는다'라는 조건을 인지해야 한다.

내가 이걸 놓쳐서 시간좀 날렸다.

일단 초기에 dp테이블은 -1로 초기화를 해준다.

 

DFS탐색은 먼저 현재인덱스의 숫자를 포함 안시킨경우를 구해본다.

즉, 아예 구하려는 구간합에 현재인덱스를 배제해버리는 것이다.

그러기 때문에 생성카운트(createCount)는 보존하면서 인덱스만 다음인덱스로 넘어가는 것이다.

(  DFS(index+1, createCount)  )

아예 없는수로 쳐버리는 것이다.

 

그다음은 현재인덱스의 수를 포함하는 경우이다.

더 정확히 말하면, 현재 인덱스를 새 그룹의 시작점으로 지정한 경우이다.

모든 경우를 탐색해야하기 때문에 위 코드의 35~39라인처럼 코드를 작성하게 된다.

 

현재 그룹에 현재 인덱스수만 포함시키고, 현재까지의 sum값 + 새로운 그룹으로의 탐색을 진행해서 최대값을 구해야하기 때문에 DFS(i + 2, createCount-1)을 진행하게 된다.

문제에서의 기본테스트케이스인

 

-1 3 1 2 4 -1          같은 경우,  첫번쨰인덱스인 -1만의 새로운그룹을 지정하고(크기가 1인), +2번째 인덱스인 1부터 새로 탐색을 진행하는 것이다.

 

그다음은 현재인덱스의 +1번째까지 포함시킨 새로은 그룹을 지정하고, +2번째인덱스인 2부터 새로 탐색을 진행하는 것이다.

 

즉, -1과 3이 한 그룹이되고 2부터 새로 탐색한값을 합친것을 비교테이블에 올리는 것이다.

이런식으로 n번까지 반복문을 진행하면서 값을 계속 갱신해주면 된다.

 

그리고 DFS함수내에서의 return 조건이 중요한데, 반드시 createCount에 대한 조건을 먼저 명시해줘야 한다.

문제에서는 반드시 m개만큼의 그룹을 만들어야한다는 조건 때문이다. 그러니 createCount가 전부 잘 소모가 됐다면 0을 리턴해줘야 반복문내에서 값갱신이 정상적으로 이루어진다.

 

이후에 index가 범위를 넘어섰을 경우의 if문을 달아서 범위를 넘어섰다면 매우작은쓰레기값을 리턴해줌으로써, 호출바로직전의 반복문안의 비교문에서 해당 값자체를 무효화시켜야 한다. 즉, result의 기존값을 유지시켜줘야 한다.

 

이게 왜 순서가 중요하냐면, 반복문안에서 다음 DFS를 호출할 때 index+2, createCount+1 이런식으로 호출하기 때문에

특정 DFS가 호출됐을 때 index가 범위를 넘어섬과 동시에 createCount도 m값을 넘어설 수 있다.(즉 정상적으로 전부 소모)

 

근데 index범위체크를 먼저해서 쓰레기값을 리턴해버리면, 정상적인값을 리턴해야함에도 불구하고 쓰레기값이 리턴되서 해당 비교자체가 무효화되버려서 정상적인 값이 갱신이 안된다.

이미 createCount가 m값을 넘어선 DFS가 호출된 시점에서, 해당 호출전에 m개의 그룹을 모두 만들었기 때문에 그냥 더 포함시킬 값이 없다는 의미로 0을 리턴해줘야 한다.

 

이 생성카운트 if문을 통과한다음에 index범위 검사를 할때, 범위를 벗어났다면 m개의 그룹도 못만들면서 index가 범위까지 벗어났다는 의미이니 아예 무효화되어야 한다. 그래서 쓰레기값을 리턴하는 것이다.