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

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

( 문제 바로가기 )

[ 이 문제에 대한 보다 구체적인 풀이를 다시 포스팅 하였습니다.

  아래의 글을 읽으셔도 문제를 푸는데 무관하지만, 보다 구체적인 설명을 원하시는 분은

  아래의 링크를 이용해주시면 감사하겠습니다.

  ( 백준 스티커(9465) 풀이 바로가기 ) ]

[ 문제풀이 ]

1. 스티커를 떼야 하는데, 상하좌우로 인접한 스티커는 찢어지게 된다. 그렇다면 아래 그림을 통해서 생각을 한번 해보자.

  위의 그림은 문제에 있는 그림에서 점수만 따온 것이다. 만약 노랑색으로 칠해진 50점이 적힌 스티커를 가장 먼저 뗀다고 가정해

  보자. 그렇다면 2번째로 떼어낼 수 있는 가장 가까운 스티커는 무엇일까?

  오른쪽 아래 대각선쪽에 있는 50점 짜리 스티커일 것이다. 왜냐하면 노랑색으로 칠해진 50점짜리 스티커를 떼는 순간

  아래에 있는 30점과 오른쪽에 있는 10점은 찢어질 것이기 떄문이다. 그 다음은? 오른쪽 위 대각선에 있는 100점짜리 스티커,

  다음은 우측하단의 10점짜리, 마지막은 40점짜리 스티커일 것이다.

  시작점을 초록색으로 칠한 경우, 반대로 생각해보면 된다.

 

  위에서 말한 내용을 그림으로 칠해보면 이렇게 더하면 된다는 결론이 난다. 그렇다면, 무조건 대각선에 있는 스티커들을

  떼어낸다면 최대값이 나올까? 문제에 주어진 예제입력만 봐도 알겠지만 최대값이 나오지 않는다.

  그렇다면 처음부터 다시 생각해보자. 노랑색이 칠해진 50점에서 두 번째로 뜯을 수 있는 스티커는 우측하단의 50점짜리

  스티커 하나 뿐일까? 아니다. 단지, 가장 많은 스티커를 떼어내기 위해서 떼어낼 수 있는 가장 가까운 스티커를

  찾은 것일 뿐, 떼어낼 수 있는 스티커는 초록색으로 칠해진 30점, 오른쪽의 10점짜리 스티커를 제외한 모든 스티커를

  선택할 수 있다. 그렇다면, 우측하단의 50점짜리 스티커 말고 오른쪽으로 2칸 옆에 있는 100점 짜리 스티커를 선택한다고

  생각해보자. 그런데.. 100점짜리 스티커를 바로 선택할 바에 처음에 말한것 처럼 50점짜리 스티커를 거쳐서 100점으로

  오는게 더 큰 값이 나오지 않을까? 맞다. 굳이 중간에 50점짜리 스티커를 건너뛰고 100점으로 올 필요가 없다. 중간에 50점짜리

  스티커를 뗴어내고 오더라도 100점짜리 스티커는 떼어낼 수 있고, 오히려 점수는 더 커질 것이기 떄문이다.

  그럼 100점짜리 말고, 70점 짜리 스티커를 떼어내는 것으로 생각해보자.

  노랑색으로 칠해진 50점 짜리 스티커 -> 두 번째줄의 3번째 값이 70점짜리 스티커를 떼어낸다면... 새로운 값을 도출해 낼 수

  있을 것 같다.

  이번에는 70점짜리 스티커 말고 2번째 줄의 4번쨰 값인 10점짜리 스티커를 떼어낸다고 생각해보자. 이 경우도 보면 알겠지만

  100점짜리 스티커를 떼는 경우가 마찬가지로, 50 -> 50 -> 100 -> 10 이 과정을 통해서 올 수 있다. 굳이 바로 10점짜리를

  떼어내면서 최댓값을 찾을 필요가 없다. 이 쯤 되면 대충 규칙을 찾았을 것이다.

  시작 스티커를 기준으로, 우측 하단의 스티커를 선택하는 경우 & 우측 하단 한칸 옆의 스티커를 선택하는 경우

  즉, 이 두가지 경우에 대해서만 생각해 주면 된다.

 노랑색 스티커에서 파랑색 스티커로 가는경우 or 노랑색 스티커에서 초록색 스티커로 가는경우, 이 두가지 경우에 대해서만

 고려를 해준다면 최대값이 나올 것이다. 그렇다고 무조건 노랑색 스티커를 선택해야 하나? 물론 그것도 아니다.

 노랑색 스티커인 50점짜리 스티커 말고, 두 번째 줄의 첫번쨰 스티커인 30점짜리를 선택해도 생각해야 될 경우의 수는 같다.

2. 먼저 나는 값을 저장하는 Arr[][] 2차원 배열을 사용하였다.

   Arr[a][b]의 의미는 a번째 줄의 b번째 스티커의 점수 이다.

   그리고 최댓값을 관리하기 위해서 DP[][] 2차원 배열을 사용하였다.

   DP[a][b]의 의미는 a번째 줄의 b번쨰 스티커를 선택했을 때의 최댓값 이다.

   초기식을 적어보자면, 나는 카드의 번호를 1번부터 시작했고, 줄은 0번째줄 1번쨰줄 이렇게 2줄을 사용했다. 

   DP[0][0] = DP[1][0] = 0 (0번째 카드는 없으므로) , DP[0][1] = Arr[0][1] , DP[1][1] = Arr[1][1] 이 된다.

3. 위의 초기식을 이용해서 이제 스티커의 최대값을 구현해야 하는데, 사실 코드는 위의 설명과 반대되도록 구현을 해야한다.

   왜냐하면 위의 그림대로라면 DP[0][1] = 50 이 될 것이다. 이는 즉, 0번째줄의 1번 카드를 뽑았을 때의 최댓값 을 의미한다.

   그렇다면, 위의 그림대로 파랑색칸 50을 선택한다면 우리가 DP[1][2] 라는 값을 알아야 한다는 말인데, 아직 선택하지도

   않은 카드를 선택했을 때의 최댓값을 알 수가 없기 때문에 반대로 구현해 줘야 한다.

   즉, DP[0][N] = DP[1][N-1] vs DP[1][N-2] 혹은 DP[1][N] = DP[0][N-1][N-2] 이렇게 !

   이 식을 충족시키기 위해서 초기식이 필요한 것이다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N;
int Arr[2][MAX];
int DP[2][MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Initialize()
{
    memset(Arr, 0, sizeof(Arr));
    memset(DP, 0, sizeof(DP));
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i <= 1; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            cin >> Arr[i][j];
        }
    }
}
 
void Solution()
{
    DP[0][0] = DP[1][0] = 0;
    DP[0][1] = Arr[0][1];
    DP[1][1] = Arr[1][1];
 
    for (int i = 2; i <= N; i++)
    {
        DP[0][i] = Bigger(DP[1][i - 1], DP[1][i - 2]) + Arr[0][i];
        DP[1][i] = Bigger(DP[0][i - 1], DP[0][i - 2]) + Arr[1][i];
    }
    cout << Bigger(DP[0][N], DP[1][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;
}