문제 출처

1. 문제설명

  • 어떤 스티커에 점수를 매기고 점수의 합이 최대가 되도록 스티커 집합을 구하려고 한다.
  • 2N개의 스티커는 한 장을 떼면, 인접한 변의 스티커는 모두 찢어져 사용할 수 없게 된다.



2. 알고리즘 설계

  • N이 1인 경우
    • 인접한 변을 고려하지 않아도 되므로, 해당 값과 같다.
  • N이 2인 경우
    • 대각선 방향의 스티커를 취할 수 있다.
    • (1,1), (2,2) 또는 (1,2), (2,1)
  • N이 3 이상인 경우
    • 현재 위치의 스티커와 대각선 방향의 스티커 또는 2칸뒤의 동일 선상의 스티커를 뗄 수 있다.
  • 점화식
    • 상단 스티커 : DP[0][i] = arr[0][i] + max(DP[1][i-1], DP[1][i-2])
    • 하단 스티커 : DP[1][i] = arr[1][i] + max(DP[0][i-1], DP[0][i-2])



3. 전체 코드

#include <bits/stdc++.h>
using namespace std;

const int SZ = 100000;
int TC, n, arr[2][SZ], DP[2][SZ];

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> TC;
	while(TC--) {
		cin >> n;
		for(int i=0; i<2; i++)
			for(int j=0; j<n; j++)
				cin >> arr[i][j];
		
		DP[0][0] = arr[0][0];
		DP[1][0] = arr[1][0];
		DP[0][1] = arr[0][1] + arr[1][0];
		DP[1][1] = arr[1][1] + arr[0][0];
		
		for(int i=2; i<n; i++) {
			DP[0][i] = arr[0][i] + max(DP[1][i-1], DP[1][i-2]);
			DP[1][i] = arr[1][i] + max(DP[0][i-1], DP[0][i-2]);
		}

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



4. 소감

  • 스티커의 인접한 방향을 이해하고, 제외시킬 수 있다면
  • 로직을 그대로 설계해 풀 수 있는 문제였다.