[Algorithm]Baekjoon 2616번 :: 소형기관차

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

2616번: 소형기관차

#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 sum[50001] = { 0 };
int dp[4][50001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    
    for (int i = 1; i <= n; ++i)
    {
        int input;
        cin >> input;
        
        sum[i] = sum[i - 1] + input;
    }
 
    cin >> m;
 
    for (int i = 1; i <= 3; ++i)
    {
        for (int j = i * m; j <= n; ++j)
        {
            dp[i][j] = max(dp[i][j - 1], dp[i - 1][j - m] + sum[j] - sum[j - m]);
        }
    }
 
    cout << dp[3][n];
}

 

 

n개의 연속된 숫자가 주어졌을 때, 최대 m개짜리 부분연속숫자의 최대값 3개를 구하는 문제이다.

부분연속값 3개를 구해야하기 때문에 m의 최대크기는 n/3이다.

n값은 최대 50,000이기 때문에 일일이 구하려면 당연히 시간초과다.

예를들어 n값이 5만이고 m값이 2라고 가정하자. 여기서 한번 일일이 구해보자.

첫블럭을 1~2로 잡고 두번째를 3~4, 세번째는 5~6부터 시작해서 7~8,9~10,...... 49,999~50,000 까지.

50000번에서 살짝 모자른정도다. 근데 여기서 두번째를 4~5로 잡고 세번째를 다시 6~7부터 시작해서 또 50,000까지 해야한다.

 

이런 많은 실행속에서 중복되는부분이 어디일까? 바로 특정구간에서의 부분블럭 최대값이다.

바로 위의 예시만 보더라도 세번째블럭의 경우 점점 시작지점이 커지긴 하지만, 대충 생각해도 25000~50000구간의 두개짜리 연속블럭값을 최소 만번이상 넘게 중복계산을 한다.

뭔 소리냐면, 두번째를 3~4로 설정한다음 세번째를 쭉 고르다보면 25000 ~25001도 붙여볼 것이고 25001 ~ 25002도 붙여볼 것이다. 근데 두번째를 6~7로 잡더라도 세번째를 쭉 고르다보면 또 25000 ~ 25001도 붙여볼 것이고 25001~25002도 붙이게 된다.

 

여기서 중복된 부분이 발생한다는 것이다. 여기서 중복된부분을 제거해줘야 한다.

이렇게 중복된부분이 발생하는곳을 알고 어떻게 제거할것인지 고민을 해야 점화식을 생각할 수 있는 것이다.

물론 일부dp문제들은 작은값들을 먼저 업데이트할 때, 우연히 패턴을 발견해서 점화식을 구할수도있긴 하지만, 사실상 운에 맡기는 방법이기 때문에 확실한거 아니면 이런식으로 푸는건 지양하자.

 

어쨌든 중복된부분을 제거하기위해서는 특정인덱스까지 부분블럭의 최대값을 계속 들고있어야 한다.

예를들어

50 40 30 20 10

이 있고 m이 2라고 가정하면, 처음 50+40을 계산한값이 배열 끝까지 갔을때 포함해서 가장 큰값이라는것을 한번의 접근(O(1))로 알아내야 한다.

 

근데 우리는 총 3개의 블럭을 구해야 한다. 그렇기 때문에 dp[i][j] 처럼 2차원으로 관리해야 한다.

즉

 

dp[i][j] =   j번째 인덱스까지 i번 부분블럭(즉 i개의 부분블럭) 를 선택했을 때의 최대값.

 

예를들어 dp[2][10] 이면 1 ~ 10번째 인덱스의 범위내에서 부분블럭(소형기관차)를 두개 선택했을 때 얻을 수 있는 최대값이다.

문제에선 3개의 소형기관차라 했으니, 종국에는 dp[3][n]을 출력해야할 것이다.

 

먼저 소형기관차를 1개만 선택해도 될 때. 각 인덱스까지의 부분블럭값의 최대값 업데이트 해준다.

그러면 앞서 말했다시피 한번의 접근으로 각 인덱스까지의 1개짜리 소형기관차의 최대값을 알 수 있게 된다.

 

이제 소형기관차를 두개 선택해야한다고 생각해보자. 두번째 소형기관차이기 때문에 시작위치는 반드시 2 * m이 된다.

첫번째 소형기관차 크기보다 작으면 겹쳐지기 때문에 당연히 안된다.

어쨌든 시작은 2*m이고 (마찬가지로 소형기관차를 세개 선택해야한다면 3*m이 시작위치다), 각 구간마다 해당 구간을 선택했을 때와 안했을때의 값 중 최대값을 dp테이블에 업데이트해주면 된다.

 

현재 구간을 선택 안했다는 것은, m개크기만큼의 블럭을 포함안시켰다는 거니까 그냥 dp[i][j-1]값이 된다. 즉, 바로 이전인덱스의 최대값이 해당된다.

 

현재 구간을 선택 했다는 것은, m개크기만큼의 블럭을 사용하겠다는 거니까 dp[i-1][j-m] + sum[j] - sum[j-m]값이 해당된다.

j-m이 뭔소리냐면, 현재 인덱스가 j라면 m개크기만큼의 블럭을 사용해야하니까 j-m부터 j까지 사용한다는 뜻이다.

j부터 j+m이 아니다. j-m부터 j다. 인덱스 0부터 업데이트했기 때문이다.

 

sum은 누적합배열이다. 처음에 미리 만들어 놓고, 특정 구간의 연속값을 구하기위해 sum[j] - sum[j-m]을 하는것이다. (이정돈 기본으로 알것이라 생각)

 

예를들어 현재 소형기관차2개이면서 인덱스 7이, m이 2라면

dp[2][7] = max(dp[2][6], dp[1][5] + sum[7] - sum[5]);    가 된다.

 

현재껄 선택안하던가(dp[2][6]), 선택하던가 ( dp[1][5] + sum[7] - sum[5](즉 6부터7까지 연속값) ).

 

dp[1][5]에는 5번째 인덱스까지 한개짜리 부분연속의 최대값이 들어있기 때문에, 현재껄 선택했을때 상정할 수 있는 최대값을 비교할 수 있게 되는 것이다.

 

최종적으로 점화식은

dp[i][j] = max(dp[i][j-1], dp[i-1][j-m] + sum[j] - sum[j-m]);

이 된다.

 

 

위 코드를 탑다운방식으로 풀이한 코드는 다음과 같다.

 

#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 sum[50001] = { 0 };
int dp[4][50001] = { 0 };
 
 
int DFS(int trainCount, int index)
{
    if (trainCount == 0) return 0;
    if (index < trainCount * m) return 0;
    if (dp[trainCount][index] != 0) return dp[trainCount][index];
 
    int result = 0;
 
    result = max(DFS(trainCount, index - 1), DFS(trainCount - 1, index - m) + sum[index] - sum[index - m]);
 
    return dp[trainCount][index] = result;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
    
    for (int i = 1; i <= n; ++i)
    {
        int input;
        cin >> input;
        
        sum[i] = sum[i - 1] + input;
    }
 
    cin >> m;
 
    cout << DFS(3, n);
}