C++ / 백준 / 9465 / 스티커

문제

https://www.acmicpc.net/problem/9465

9465번: 스티커

 

문제풀이

스티커는 하나를 골랐으면 바로 옆 대각선 1칸의 스티커밖에 고르지 못한다.

또는 오른쪽 스티커를 아예 고르지 않고 2칸 옆에 있는 스티커를 고를 수 있다.

왼쪽부터 오른쪽으로 진행하면서 스티커를 고른다고 가정해보자.

가운데에 있는 70원짜리를 고르려고 할 때, 50+70=120의 경우와 30+10+70=110의 경우가 있다.

이를 식으로 세우면 DP[1][x]=70 + max(DP[0][x-2], DP[0][x-1])라는 식이 나온다.

1열은 자기 자신, 2열은 왼쪽 대각선 방향 스티커+자기 자신이므로 직접 입력해준다.

3열부터는 끝열까지

DP[0][x] = Arr[0][x] + max(DP[1][x - 2], DP[1][x-1])

DP[1][x] = Arr[1][x] + max(DP[0][x - 2], DP[0][x-1])

두 식을 반복문을 돌려 최댓값을 저장한다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int T = 0;
	int n = 0;
	int y = 0, x = 0;
	cin >> T;
	while (T--) {
		cin >> n;
		vector<vector<int>>DP(2, vector<int>(n, 0));
		vector<vector<int>>Arr(2, vector<int>(n, 0));
		for (y = 0; y < 2; ++y) {
			for (x = 0; x < n; ++x) {
				cin >> Arr[y][x];
			}
		}
		DP[0][1] = Arr[0][1] + Arr[1][0];
		DP[1][1] = Arr[0][0] + Arr[1][1];
		DP[0][0] = Arr[0][0];
		DP[1][0] = Arr[1][0];

		for (x = 2; x < n; ++x) {
			DP[0][x] = Arr[0][x] + max(DP[1][x - 2], DP[1][x-1]);
			DP[1][x] = Arr[1][x] + max(DP[0][x - 2], DP[0][x-1]);

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

}