[Baekjoon] 백준 9465번 스티커

9465번 스티커 문제 풀이

문제

• 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.
  상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 서로 변을 공유 하지 않는 스티커 집합을 구해야 한다.

입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 점수이다. 연속하는 두 정수 사이에는 빈 칸이 하나 있다. 점수는 0보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

• 각 테스트 케이스 마다, 2n개의 스티커 중에서 두 변을 공유하지 않는 스티커 점수의 최댓값을 출력한다.

예제

입력
2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80

출력
260
290

코드

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;

int score[3][100001];
int d[3][100001];

int main() {
    int t; 
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        for (int i = 1; i <= 2; i++) {
            for (int j = 1; j <= n; j++) {
                cin >> score[i][j];
                d[i][j] = 0;
            }
        }
        d[1][1] = score[1][1];
        d[2][1] = score[2][1];
        for (int i = 2; i <= n; i++) {
            d[1][i] += max(d[2][i - 1], d[2][i - 2]) + score[1][i];
            d[2][i] += max(d[1][i - 1], d[1][i - 2]) + score[2][i];
        }

        cout << max(d[1][n], d[2][n]) << '\n';
    }
    return 0;
}

해결방법

O	X	O	X	O	X	O	X	O	X
X	O	X	O	X	O	X	O	X	O

X	O	X	O	X	O	X	O	X	O
O	X	O	X	O	X	O	X	O	X

O	X	X	O	X	X	O	X	O	X
X	X	O	X	X	O	X	O	X	O

O	X	X	O	X	X	O	X	O	X
X	X	X	X	X	O	X	O	X	O

• 첫번째와 두번째처럼 한 칸씩 대각선으로 건너뛰며 점수를 계산하는 방법과 세번째처럼 두칸을 건너 뛰어서 점수를 계산할 수도 있다.

• 두칸을 건너 뛸때와 한칸을 건너 뛸때 방문할 수 있는 지점은 달라질 수 있지만 세 칸을 건너뛰는 경우는 1,2,3번째 표의 경우로도 항상 방문할 수 있는 지점이기 때문에 최대값을 구할 수 업다.

• 따라서 (0,1)번 지점에서 시작하는 경우와 (1,0)에서 시작하는 경우에 대해서 한 칸을 건너뛰었을 때의 합과 두 칸을 건너뛰었을 때의 합에 대한 최대값을 구하여 마지막 이동 지점의 점수를 더해주는 점화식을 세워 마지막 도달지점인 (0,N), (1,N)두 곳중에 최대값을 찾아 출력한다.

        for (int i = 2; i <= n; i++) {
        d[1][i] += max(d[2][i - 1], d[2][i - 2]) + score[1][i];
        d[2][i] += max(d[1][i - 1], d[1][i - 2]) + score[2][i];
        }
  
        cout << max(d[1][n], d[2][n]) << '\n';