백준 9465번 스티커

문제 링크입니다: https://www.acmicpc.net/problem/9465

동적계획법이라고는 했지만 거의 완전탐색법으로 푼 문제였습니다.(그 결과 실행속도...)

핵심은 전 대각선과 전전 대각선만 비교하면 된다는 것이였습니다.

/*

상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다.

스티커는 그림(a)와 같이 2행 n열로 배치되어 있다.상냥이는 스티커를 이용해 책상을 꾸미려고 한다.

상냥이가 구매한 스티커의 품질은 매우 좋지 않다.

스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다.

즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.

모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다.

즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

*/

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 100000 + 1;

 

int sticker[MAX][2];

int cache[MAX][2];

int N; //가로의 길이

 

int maxScore(void)

{

        cache[0][0] = cache[0][1] = 0; //초기값(원래 스티커는 idx=1 부터 시작)

        cache[1][0] = sticker[1][0];

        cache[1][1] = sticker[1][1];

        //위에서 시작하는 것과 아래에서 시작하는 경우를 비교하면 된다

        for (int i = 2; i <= N; i++)

        {

               //그 전칸 대각선을 선택하는 경우 vs 그 전칸 대각선을 선택하지 않고 그 전전칸 대각선을 선택하는 경우

               cache[i][0] = max(cache[i - 1][1], (i - 2 > 0) ? cache[i - 2][1] : 0) + sticker[i][0];

               cache[i][1] = max(cache[i - 1][0], (i - 2 > 0) ? cache[i - 2][0] : 0) + sticker[i][1];

        }

        return max(cache[N][0], cache[N][1]);

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

       

        for (int i = 0; i < test_case; i++)

        {

               cin >> N;

               if (N<1 || N>=MAX)

                       exit(-1);

 

               for (int i = 0; i < 2; i++)

                       for (int j = 1; j <= N; j++)

                              cin >> sticker[j][i];

               cout << maxScore() << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~