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

백준의 스티커(9465) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

하나의 예시를 통해서 문제에 접근해보자.

.

위와 같은 스티커맵이 주어졌다고 가정해보자.

그리고 지금부터 하는 이야기들을 간편하게 표현하기 위해서 몇 가지 표현 방식에 대해서만 정리해보자.

1. 편의상 윗줄을 1층으로, 아랫줄을 2층으로 표현하자.

2. 스티커를 가장 왼쪽에서부터 1 ~ 5번으로 표현하자.

3. F[A][B] = C 라는 수식을 사용해서 각 스티커를 뗐을 때 얻을 수 있는 최대점수를 나타내자.

   F[A][B] = C의 의미는 "A층에 있는 B번째 스티커를 뗐을 때, 얻을 수 있는 최대점수는 C점입니다." 이다.

   ex) F[1][1] = 10. => "1층에 있는 1번째 스티커를 뗐을 때, 얻을 수 있는 최대점수는 10점입니다."

이제 위의 표현방식들을 이용해서 문제에 접근해보자.

가장 간단하게, 1층에 있는 1번 스티커, 2층에 있는 1번 스티커 부터 차례대로 스티커를 떼어내보자.

즉 ! 왼쪽에서부터 오른쪽으로 , 층수는 1층에서부터 2층으로 가는 순서대로 스티커를 한번 떼어내보자.

# 1층에 있는 1번 스티커를 떼는 경우 : F[1][1]

이 경우에는 별 다른 선택권이 없다. 기존에 떼어낸 스티커가 없기 때문에 당연히 저 스티커를 뗐을 때 얻을 수 있는

최대점수는 (1, 1)에 존재하는 '10점' 이 된다.

F[1][1] = 10

# 2층에 있는 1번 스티커를 떼는 경우 : F[2][1]

이 경우에는 1층에 있는 1번 스티커를 뗄 수가 없다. 2층에 있는 1번 스티커를 떼어냈을 때 얻을 수 있는 최대점수는 15점이

된다.

F[2][1] = 15

# 1층에 있는 2번 스티커를 떼는 경우 : F[1][2]

1층에 있는 2번 스티커를 떼기 위한 방법으로는 총 2가지 방법이 있다.

1. 2층에 있는 1번 스티커를 뗀 후에, 1층에 있는 2번 스티커를 떼는 경우

2. 1층, 2층에 있는 1번 스티커 2개 모두 떼어내지 않고, 1층에 있는 2번 스티커만을 떼는 경우

위와 같이 2가지 Case가 존재한다.

보기 쉽게 그림으로 나타내보면 다음과 같은 2가지 경우가 존재한다는 것이다.

.

위의 그림에서 노랑색 동그라미는 "떼어내는 스티커"를 의미한다.

1번 Case같은 경우는 2개의 그림 중 위에 있는 그림처럼 2개의 스티커를 떼어내는 경우를 의미하고

2번 Case같은 경우는 2개의 그림 중 아래에 있는 그림처럼 1개의 스티커만을 떼어내는 경우를 의미한다.

각각의 Case들을 계산해보면

1번 Case : 15 + 11 = 26점.

2번 Case : 11점.

따라서 1층에 있는 2번 스티커를 떼는 경우, 얻을 수 있는 최대 점수는 1번 Case가 갖는 점수인 '26점'이 된다.

F[1][2] = 26

# 2층에 있는 2번 스티커를 떼는 경우 : F[2][2]

2층에 있는 2번 스티커를 떼기 위한 방법으로는 총 2가지 방법이 있다.

1. 1층에 있는 1번 스티커를 뗀 후에, 2층에 있는 2번 스티커를 떼는 경우

2. 1층, 2층에 있는 1번 스티커 2개 모두 떼어내지 않고, 2층에 있는 2번 스티커만을 떼는 경우

그림으로 나타내면 다음과 같다.

.

각각의 Case들을 계산해보면

1번 Case : 10 + 14 = 24

2번 Case : 14

따라서 2층에 있는 2번 스티커를 떼는 경우, 얻을ㅇ 수 있는 최대 점수는 1번 Case가 갖는 점수인 '24점'이 된다.

F[2][2] = 24

# 1층에 있는 3번 스티커를 떼는 경우 : F[1][3]

1층에 있는 3번 스티커를 떼어내는 경우를 먼저 한번 살펴보자. 이해하기 쉽게 각각의 방법들과 함께 그림으로 알아보자.

Case1 : 1층 1번스티커 + 2층 2번스티커 + 1층 3번스티커

.

Case2 : 1층 1번스티커 + 1층 3번스티커

.

Case3 : 2층 2번스티커 + 1층 3번스티커

.

Case4 : 2층 1번스티커 + 1층 3번스티커

.

위와같이 총 4가지 경우가 있다. 물론 더 있을 수는 있지만, 그 경우들은 절대로 최대점수를 얻는 경우들은 아닐 것이다.

왜 그런지는 위의 Case들에 대한 내용들을 이야기하면서 이해해보자.

먼저 위의 경우들을 모두 비교해볼 필요가 있는지에 대해서 부터 알아보자.

Case2와 Case3 그리고 Case1을 비교해보자.

문제에서 제시한 스티커의 점수는 0보다 크거나 같은 정수이다. 즉 ! 음수는 존재하지 않는다는 것이다.

이 말은 ! 다시 말해서 스티커를 떼어냄으로써 점수가 깎이는 경우는 존재하지 않는다는 것이다.

최소 그 점수가 그대로 유지되기는 하더라도 , 점수가 오히려 깎이지는 않는다는 것을 의미한다.

그럼 Case1과 Case2, Case3을 비교해보자.

과연 ! Case2, Case3이 Case1보다 더 큰 점수를 가질 수가 있을까 ???

절대로 가질 수가 없다. 왜?? Case2와 Case3 같은 경우에는 "떼어낼 수 있는 스티커가 더 있음에도 떼어내지 않은 경우" 에 속하기 때문이다. 그림으로 보면 아래와 같기 때문이다.

Case2 : 1층 1번스티커 + 1층 3번스티커

.

Case3 : 2층 2번스티커 + 1층 3번스티커

.

위의 그림들에서 '빨강색 동그라미' 들로 표시된 스티커를 떼어낼 수 있음에도 떼어내지 않았기 때문에 절대로 최대 점수가 나올 수가 없는 Case들이다.

Case4같은 경우에는 이야기가 좀 다르다.
.

Case4가 위의 경우인데, 이 경우에는 '2번 스티커' 2개를 모두 떼어낼 수가 없다. 왜냐하면, 2층에 있는 1번스티커를 떼어냄으로써 2층에 있는 2번 스티커를 떼어낼 수 없게 되고, 1층에 있는 3번 스티커를 떼어냄으로써 1층에 있는 2번 스티커를 떼어낼 수가 없게 된다.

위에서 언급한 "더 많은 경우가 있을 수 있지만, 그 경우들은 절대로 최대점수를 얻지 못할 것이다" 라는 이유도 여기에 있다.

Case2, 3과 같이 더 많은 스티커를 떼어낼 수 있음에도 떼어내지 않은 경우들을 모두 찾는다면 더 많은 경우들이 있을 수 있지만, 그 경우들은 절대로 최대점수를 얻게 되지 못한다.

그럼 결과적으로 우리가 비교해야 하는 Case는 2개로 간추려진다. 바로 Case1과 Case4.
.
.

결과적으로 위의 2가지 경우를 비교해야 한다는 것을 의미한다. 지금부터는 위의 4개의 Case는 모두 잊어버리고 최종적으로 남은 위의 2개의 Case들을 순차적으로 Case1, 2로 표현하겠다.

먼저, 1번 Case를 수식으로 나타내면, "1층에 있는 1번스티커 + 2층에 있는 2번스티커 + 1층에 있는 3번 스티커" 인데,

여기서 "1층에 있는 1번 스티커 + 2층에 있는 2번 스티커" 를 한번 보자. 이 값은 우리가 이미 기존에 구해놨던 값이다.

바로 F[2][2] 이다. 저렇게 스티커 떼는 경우 하나하나를 계산할 필요 없이, "2층에 있는 2번 스티커를 떼어냈을 때, 얻을 수 있는 최대점수"만 알 수 있다면, 이 점수에 "1층에 있는 3번 스티커"를 떼어냄으로써 얻을 수 있는 점수를 더해주기만 하면 된다.

즉 ! Case1을 정리해보면 "1층에 있는 3번 스티커를 떼어낼 때 얻을 수 있는 최대 점수는, 2층에 있는 2번 스티커를 떼어낼 때 얻을 수 있는 최대점수 + 1층에 있는 3번 스티커의 점수" 가 된다는 것이다.

Case2 또한 "2층에 있는 1번 스티커를 떼어냄으로써 얻을 수 있는 최대점수 + 1층 3번 스티커의 점수" 로 이 값을 구할 수가 있다.

그럼 우리가 사용하는 수식으로 표현해보면 F[1][3]의 값은

F[1][3] = Max(F[2][2] , F[2][1]) + Sticker[1][3] 이 된다는 것이다.

그럼 ! 여기서 3번 스티커가 아닌 N번 스티커로 바꿔보자. 그럼 위의 식이 어떻게 바뀌게 될까 ?? 바로

F[1][N] = Max(F[2][N - 1], F[2][N - 2]) + Sticker[1][N] 이 된다.

반대의 경우도 마찬가지이다. 2층에 있는 3번 스티커를 떼어내는 경우, 즉 ! F[2][3]의 값을 구한다면, 위의 수식이 어떻게 바뀌게 될까 ?? 바로 ! 층수만 바꿔주면 된다.

F[2][3] = Max(F[1][2] , F[1][1]) + Sticker[2][3]

이 경우 또한, 3을 N으로 바꿔본다면

F[2][N] = Max(F[1][N - 1], F[1][N - 2]) + Sticker[2][N] 이 된다는 것이다.

이를 점화식으로 사용해서 구현해 주었다.

위에서 사용한 수식 F[][] 처럼, 2차원 배열을 하나 만들어서 F[][]의 값을 표현해 주었다.

최종적인 결과값은, F[1][N]과, F[2][N] 중 더 큰 값이 최대점수가 된다.

[ 소스코드 ]

#include <iostream>
#include <cstring>
 
#define endl "\n"
#define MAX 100010
using namespace std;
 
int N;
int MAP[3][MAX];
int DP[3][MAX];
 
int Max(int A, int  B) { if (A > B) return A; return B; }
 
void Initialize()
{
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= 2; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
void Solution()
{
    DP[1][1] = MAP[1][1];
    DP[2][1] = MAP[2][1];
    for (int i = 2; i <= N; i++)
    {
        DP[1][i] = Max(DP[2][i - 1], DP[2][i - 2]) + MAP[1][i];
        DP[2][i] = Max(DP[1][i - 1], DP[1][i - 2]) + MAP[2][i];
    }
    cout << Max(DP[1][N], DP[2][N]) << endl;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}