[boj] (s1) 9465 스티커

47357 단어 bojboj

✅ dp ✅ Bottom Up

문제

링크

풀이

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

  • 인접한 스티커는 선택할 수 없다.
    • 대각선에 위치한 스티커만 선택 가능
    • 한 행에 하나의 스티커만 선택 가능
  • 정의
    f(i,j)=i,jf(i,j)=i,j
  • 구하는 답
    max(f(0,n1),f(1,n1)),(0:i,1:j)max(f(0,n-1),f(1,n-1)),(0:i,1:j)
  • 초기값
    f(0,0)=sticker[0][0]f(0,0)=sticker[0][0]
  • 점화식
    f(0,j)=max(f(1,j1),f(1,j2))+sticker[0][j],(j>=2)f(0,j)=max(f(1,j-1),f(1,j-2))+sticker[0][j],(j>=2)
  • 구하는 답
    스티커를 떼는 경우는 크게 마지막 행의 윗줄을 뗄 것이냐, 아랫줄을 뗄 것이냐로 나눠질 수 있다.
    왜냐하면 스티커의 점수가 최대가 되려면 일단 많이 떼야하는데 마지막줄을 안뗄 이유가 없기 때문이다.
    따라서 스티커 점수의 최댓값은 마지막 행의 윗줄 or 아랫줄을 떼는 두가지 경우 중에 큰 값이다.

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

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

f(0,0)=50f(0,0)=50

  • 점화식
(1,j2)(1,j-2)(i,j)(i,j)
(1i,j2)(1-i,j-2)(1i,j1)(1-i,j-1)

(i,j)(i,j) 번째 스티커는 열이 다른 (1i,j2)(1-i,j-2)

왜냐하면 대각선 위치의 스티커만 선택이 가능하고, 모든 행에서 스티커를 선택해야 한다는 조건이 없으므로 (1i,j1)(1-i,j-1)

그리고 (1,j2)(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)O(N)

4. 문제에서 중요한 부분

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

좋은 웹페이지 즐겨찾기