📘 문제

문제링크 : https://www.acmicpc.net/problem/9465 (solved.ac class4)

📝 문제 풀이

처음 문제를 풀때 직관적으로 생각난 풀이는 재귀를 사용하여 모든 경우를 다 탐색하는 것이다. 하지만 시간복잡도를 생각해봤을 때 (아마 제대로 계산을 하진 못했을 거다) 시간초과가 발생할 것 같았다. 그래서 다음으로 생각한 것이 dp이다. dp로 풀때는 차근히 작은것 부터 생각해 보는 것이 좋은 방법인것 같다.
❗️n열이 주어지므로 1열부터 차근히 생각해보자.
1열에서는 단순히 50, 30 둘 중 큰 값을 비교하면된다.
2열에서는 대각선 두값을 더한 값 중 큰 값을 비교하면 된다.
3열부터는 1행3열, 2행3열 각각 앞에서 더해서 구했던 값들 중 자기 자신이 포함할 수 있는 경우 중 가장 큰값에 자기 자신을 더한 값을 구한다. 이 두값과 2열까지의 최댓값을 비교하면 된다.

이 과정을 하면서 생각난 것이 1열부터 dp를 이용해서 해당 행,열 자리는 자기자신을 포함할 수 있는 최대값으로 초기화해나가면 최댓값을 구할 수 있다라는 것이다.
즉

1열
- 자기자신을 포함했을 때 값으로 초기화
2열
- 자기자신이 포함될 수 있게 (1열 대각선 방향값 + 자신값) 으로 초기화
3열 ~ n열
- 초기화된 값들 중 (다른 행의 i-2열, i-1열중 큰값 + 자신값) 으로 초기화

코드부분

dp[0] = arr[0];
dp[n] = arr[n];
if(n>1){
    dp[1] = dp[n] + arr[1];
    dp[n+1] = dp[0] + arr[n+1];
}
if(n>2){
    for(int i=2; i<n; i++){
        dp[i] = max(dp[n+i-2],dp[n+i-1]) + arr[i];
        dp[n+i] = max(dp[i-2],dp[i-1]) + arr[n+i];
    }
}

(❗️필자는 1차원배열로 풀었으니 2차원배열로 변경해서 풀면된다.)

이렇게 n열까지 초기화한 후 마지막 두열의 4개의 숫자를 비교해서 가장 큰 값을 출력하면 된다.

✏️ 알고리즘 스케치

빨간색과 보라색을 보시면 이해하시기 편합니다.

💻 소스코드

//1.벡터코드
#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

void solution(int n, vector<int>& arr);

int main()
{
    fastio;

    int T;
    cin >> T;

    vector<int> arr;
    while(T--){
        int n;
        cin >> n;

        arr.resize(2*n);
        for(int i=0; i<2*n; i++)
            cin >> arr[i];

        solution(n,arr);
    }
    
    return 0;
}

void solution(int n, vector<int>& arr)
{
    vector<int> dp;
    dp.resize(2*n);
    
    dp[0] = arr[0];
    dp[n] = arr[n];
    if(n>1){
        dp[1] = dp[n] + arr[1];
        dp[n+1] = dp[0] + arr[n+1];
    }
    if(n>2){
        for(int i=2; i<n; i++){
            dp[i] = max(dp[n+i-2],dp[n+i-1]) + arr[i];
            dp[n+i] = max(dp[i-2],dp[i-1]) + arr[n+i];
        }
    }

    int max = 0;
    for(int i=0; i<2; i++){
        if(max<dp[n-1-i])
            max = dp[n-1-i];
        if(max<dp[2*n-1-i])
            max = dp[2*n-1-i];
    }

    cout << max << "\n";
    dp.clear();
}

//2.배열코드
#include <iostream>
#include <algorithm>
#include <vector>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

void solution(int n, int (&arr)[200000], int (&dp)[200000]);

int main()
{
    fastio;

    int T;
    cin >> T;

    int arr[200000];
    int dp[200000];

    while(T--){
        int n;
        cin >> n;

        for(int i=0; i<2*n; i++)
            cin >> arr[i];

        solution(n,arr,dp);
    }
    
    return 0;
}

void solution(int n, int (&arr)[200000], int (&dp)[200000])
{   
    dp[0] = arr[0];
    dp[n] = arr[n];
    if(n>1){
        dp[1] = dp[n] + arr[1];
        dp[n+1] = dp[0] + arr[n+1];
    }
    if(n>2){
        for(int i=2; i<n; i++){
            dp[i] = max(dp[n+i-2],dp[n+i-1]) + arr[i];
            dp[n+i] = max(dp[i-2],dp[i-1]) + arr[n+i];
        }
    }

    int max = 0;
    for(int i=0; i<2; i++){
        if(max<dp[n-1-i])
            max = dp[n-1-i];
        if(max<dp[2*n-1-i])
            max = dp[2*n-1-i];
    }

    cout << max << "\n";
}

메모리가 더 작은 줄이 배열로 작성한 코드입니다.