9465) 스티커 c++

문제 ) www.acmicpc.net/problem/9465

9465번: 스티커

 

풀이 ) 스티커는 2행 n열 이라고 해서 행렬의 행을 2로 픽스하고 시작했다.

1. 첫 번째 행의 스티커 점수를 입력받고,

2. 그 다음 행의 스티커 점수를 입력받는다. 2행이기에 가능한.

3. st는 입력받은 스티커 배열이고, dp는점수 합산용 배열이다.
   dp배열의 맨 처음 열에는 st배열의 맨처음 열 값을 넣고 시작한다.

          [0]  [1]  [2]   [3]  [4]
st[0]  50  10  100  20  40
st[1]   30  50   70   10  60

위의 배열에서 100 -> 10 이 아닌, 100 -> 60으로 가기 위한 전략이 필요하다.

4, 5 대각선의 스티커 점수를 더한 값과 이전의 값중에서 큰 값을 골라서 반복해서 연산 한뒤 가장 값을 큰걸로 산출한다.

 

코드 ) 

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

int T, N, sum;
int st[2][100001];
int dp[2][100001];

int main(int argc, char** argv) {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> T;
	while(T--) {
		cin >> N;
		for(int i=0; i<N; i++)		// 1
			cin >> st[0][i];
		for(int i=0; i<N; i++)		// 2
			cin >> st[1][i];
		
		dp[0][0] = st[0][0];		// 3
		dp[1][0] = st[1][0];
		
		for(int i=1; i<N; i++) {
			dp[0][i] = max(st[0][i] + dp[1][i-1], dp[0][i-1]);	// 4
			dp[1][i] = max(st[1][i] + dp[0][i-1], dp[1][i-1]);	// 5
		}
		cout << max(dp[0][N-1], dp[1][N-1]) << '\n';
	}
	return 0;
}