✅ dp ✅ Bottom Up

문제

링크

풀이

1. 문제 접근 및 해결 로직 (풀이법)

• 인접한 스티커는 선택할 수 없다.
  • 대각선에 위치한 스티커만 선택 가능
  • 한 행에 하나의 스티커만 선택 가능

• 정의
  $f(i,j)=i,j$ 칸을 마지막으로 골랐을 때 스티커 점수의 최댓값
• 구하는 답
  $max(f(0,n-1),f(1,n-1)),(0:i,1:j)$
• 초기값
  $f(0,0)=sticker[0][0]$
  $f(0,1)=sticker[1][0]+sticker[0][1]$
  $f(1,0)=sticker[1][0]$
  $f(1,1)=sticker[0][0]+sticker[1][1]$
• 점화식
  $f(0,j)=max(f(1,j-1),f(1,j-2))+sticker[0][j],(j>=2)$
  $f(1,j)=max(f(0,j-1),f(0,j-2))+sticker[1][j],(j>=2)$

• 구하는 답
  스티커를 떼는 경우는 크게 마지막 행의 윗줄을 뗄 것이냐, 아랫줄을 뗄 것이냐로 나눠질 수 있다.
  왜냐하면 스티커의 점수가 최대가 되려면 일단 많이 떼야하는데 마지막줄을 안뗄 이유가 없기 때문이다.
  따라서 스티커 점수의 최댓값은 마지막 행의 윗줄 or 아랫줄을 떼는 두가지 경우 중에 큰 값이다.

• 초기값
  예를들어 스티커가 다음과 같이 주어진다면

  ```
  50 10 100 20 40
  30 50 70 10 60
  ```

$f(0,0)=50$
$f(0,1)=30+10=40$
$f(1,0)=30$
$f(1,1)=50+50=100$

• 점화식

$(1,j-2)$		$(i,j)$
$(1-i,j-2)$	$(1-i,j-1)$

$(i,j)$ 번째 스티커는 열이 다른 $(1-i,j-2)$ 번째 스티커와 $(1-i,j-1)$ 번째 스티커에 따라 결정된다.

왜냐하면 대각선 위치의 스티커만 선택이 가능하고, 모든 행에서 스티커를 선택해야 한다는 조건이 없으므로 $(1-i,j-1)$ 을 건너뛰고, $(1-i,j-2)$ 에서 바로 $(i,j)$ 로 넘올 수도 있다.

그리고 $(1,j-2)$을 점화식에 포함시키지 않은 이유는 $(1-i,j-1)$에서 $(1,j-2)$가 이미 포함되기 때문이다.

dp - Bottom Up (반복문, 타뷸레이션) 사용

2. 코드

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

int T, n;
int sticker[2][100000];
int memo[2][100000];

int main()
{
    cin >> T;
    while(T--){
        memset(sticker, 0, sizeof(sticker));
        memset(memo, 0, sizeof(memo));

        cin >> n;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> sticker[i][j];
            }
        }

        memo[0][0] = sticker[0][0];
        memo[0][1] = sticker[1][0] + sticker[0][1];
        memo[1][0] = sticker[1][0];
        memo[1][1] = sticker[0][0] + sticker[1][1];

        for (int j = 2; j < n; j++)
        {
            memo[0][j] = max(memo[1][j-1], memo[1][j-2]) + sticker[0][j];
            memo[1][j] = max(memo[0][j - 1], memo[0][j - 2]) + sticker[1][j];
        }

        cout << max(memo[0][n-1], memo[1][n-1]) << "\n";
    }
    
    return 0;
}

3. 시간 복잡도 분석

경우의 수를 모두 구하므로
$O(N)$

4. 문제에서 중요한 부분

DP문제는 점화식을 도출하는 것이 중요하다.
Bottm Up(반복문)으로 풀지 Top Down(재귀)으로 풀지는 선택사항