[C++/Python] 백준 9465 - 스티커

문제 링크

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

9465번: 스티커

 

 

N이 1일 때는 아래, 위의 두 값 중 최대값이 되고

2일 때는 이전 대각선과의 합 중 최대값이 됩니다.

3이상일 때는 이전 대각선과의 합과 이전 대각선 왼쪽과의 합 중 최대값이 정답이 됩니다.

 

 

구현 코드

 

	#include <iostream>
	#include <algorithm>
	#define endl '\n'
	#define fastio cin.sync_with_stdio(false); cin.tie(nullptr);
	using namespace std;
	const int MAX = 100000;
	int dp[2][MAX];
	int main(){
	fastio;
	int test_case;
	cin >> test_case;
	while(test_case--){
	int n;
	cin >> n;
	for(int i=0;i<2;i++)
	for(int j=0;j<n;j++)
	cin >> dp[i][j];
	dp[0][1] += dp[1][0];
	dp[1][1] += dp[0][0];
	for(int j=2;j<=n;j++){
	dp[0][j] += max(dp[1][j-1], dp[1][j-2]);
	dp[1][j] += max(dp[0][j-1], dp[0][j-2]);
	}
	cout << max(dp[0][n-1], dp[1][n-1]) << endl;
	}
	return 0;
	}

view raw 9465.cpp hosted with ❤ by GitHub

	test_case = int(input())
	for _ in range(test_case):
	n = int(input())
	dp = []
	for i in range(2):
	dp.append(list(map(int, input().split())))
	dp[0][1] += dp[1][0]
	dp[1][1] += dp[0][0]
	for j in range(2,n):
	dp[0][j] += max(dp[1][j-1], dp[1][j-2])
	dp[1][j] += max(dp[0][j-1], dp[0][j-2])
	print(max(dp[0][n-1], dp[1][n-1]))

view raw 9465.py hosted with ❤ by GitHub