[백준 9465번] 스티커 (C++)

아이디어

이전에 RGB라고 비슷한 문제를 푼적이 있어서 한번에 통과가 됐다.

위가 dp보드일때, 빨간V위치에 올 수 있는 경우는 1과 2에서 올 수 있다. 2'도 가능하지만, 점수는 양수이므로 2'에서 온다면 2'-2-v로 올때보다 무조건 작은 경우 이므로 고려하지 않는다.

[ ( 2- V ) 경로와 (2'-2-V)는 2에 2'에서 오는 경로를 포함하고 있으므로. ] 

 

C++ 풀이

#include <bits/stdc++.h>

using namespace std;
int board[2][100001];
int dp[2][100003];
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;
    for(int i = 0 ; i < T; i++)
    {
        memset(board,0,sizeof(board)); //테스트 케이스별로 같은 보드라 혹시나 해서.
        memset(dp,0,sizeof(dp)); // 마찬가지. 초기화.
        int N;
        cin >> N;
        for(int j= 0 ; j<2; j++)
        {
            for(int k = 0; k<N;k++ )
            {
                int tmp;
                cin >> tmp;
                board[j][k] = tmp; // 보드를 만들어주고
            }
        }
        dp[0][0] = 0; // 아래 dp를 계산하기 위해서 0으로 셋팅해주고
        dp[0][1] = 0; // 물론 memset으로 해줬지만..
        dp[1][0] = 0;
        dp[1][1] = 0;
        for(int j = 2; j<N+2; j++)
        {
            for(int k = 0; k<2; k++)
            {
                int r = (k+1)%2; // dp의 row와 board에서 접근하는 row가 교차되므로.
                // 아이디어 그림대로 구현
                dp[k][j] =max(board[k][j-2]+dp[r][j-1], board[k][j-2]+dp[r][j-2]);
                
            }
        }
        //최종 두개를 비교해서 큰값 출력
        cout << max(dp[0][N+1], dp[1][N+1])<<endl;
        
    }
}