백준 9465 - 스티커

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

9465번: 스티커

이 문제는 다이나믹 프로그래밍(동적 계획법)의 문제로 계산했던 값을 재사용하는 방식으로 해결했습니다.

 

스티커를 하나 고른다면 그 스티커의 상하좌우 스티커는 사용할 수 없게 됩니다. 스티커에 점수가 각각 부여되었을 때 최대의 값을 가질 수 있도록 스티커를 때내는 방법을 찾아야합니다. 

 

(1,1)	(1,2)	(1,3)	(1,4)	(1,5)
(2,1)	(2,2)	(2,3)	(2,4)	(2,5)

(1,1) 과 (2,1)에서의 최댓값은 (1,1), (2,1)의 스티커의 값과 같습니다. 

(1,4)같은 경우는 최댓값의 경우의 수가 2가지 입니다. (2,3)의 최댓값+(1,4)스티커값 / (2,2)의 최댓값+(1,4)스티커값

(2,4)같은 경우는 최댓값의 경우의 수가 2가지 입니다. (1,3)의 최댓값+(2,4)스티커값 / (1,2)의 최댓값+(2,4)스티커값

맨앞의 스티커를 제외하고는 모두 2가지의 경우의 수가 나오는데, 이때 두수중 큰수를 가져오면 됩니다.

max_num[0][i] = max(max_num[1][i - 1] + stiker[0][i], max_num[1][i - 2] + stiker[0][i]);
max_num[1][i] = max(max_num[0][i - 1] + stiker[1][i], max_num[0][i - 2] + stiker[1][i]);

이러한 식으로 가져오면 각각 칸에서의 가장 큰 값을 구할 수 있습니다. 

모든 경우를 실행한뒤에 for문을 통해서 가장 큰값을 찾아주면 됩니다.

자세한 부분은 코드를 보면서 확인해주시길 바랍니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int test_case;
int stiker[2][100001] = {0,};
int max_num[2][100001] = {0,};

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int k = 0; k < test_case; k++) {
		int number_s = 0;
		int max_money = 0;
		cin >> number_s;
		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= number_s; j++) {
				cin >> stiker[i][j];
			}
		}
		max_num[0][1] = stiker[0][1];
		max_num[1][1] = stiker[1][1];
		for (int i = 2; i <= number_s; i++) {
			max_num[0][i] = max(max_num[1][i - 1] + stiker[0][i], max_num[1][i - 2] + stiker[0][i]);
			max_num[1][i] = max(max_num[0][i - 1] + stiker[1][i], max_num[0][i - 2] + stiker[1][i]);
		}
		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= number_s; j++) {
				max_money = max(max_money, max_num[i][j]);
			}
		}
		for (int i = 0; i < 2; i++) {
			for (int j = 1; j <= number_s; j++) {
				stiker[i][j] = 0;
				max_num[i][j] = 0;
			}
		}
		cout << max_money << "\n";
	}
	return 0;
}

 

질문, 조언 댓글 부탁드립니다!