[백준] 9465 스티커, python, C++

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

9465번: 스티커

그냥 대충 보면 완전탐색인것처럼 보이지만 N=100000이므로 DP 문제이다.

2행의 배열이 주어졌을때 구할수 있는 최대값을 찾는 문제이다.

 

T = int(input())
for tc in range(T):
    N = int(input())
    sticker = [list(map(int, input().split())) for _ in range(2)]

    memo = [[0 for _ in range(N)] for _ in range(2)]
    for i in range(N):
        memo[0][i] = sticker[0][i]
        memo[1][i] = sticker[1][i]
        if i == 0:
            continue
        elif i == 1:
            memo[0][i] += memo[1][i - 1]
            memo[1][i] += memo[0][i - 1]
        else:
            memo[0][i] += max(memo[1][i - 1], memo[1][i - 2])
            memo[1][i] += max(memo[0][i - 1], memo[0][i - 2])

    print(sticker, memo)

    print(max(memo[0][-1], memo[1][-1]))

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

#define max(x, y) ((x > y) ? x : y)

int main() {
	int T, N, tc, i, j, num_tmp;
	cin >> T;
	for (tc = 0; tc < T; tc++)
	{
		cin >> N;
		vector<vector<int>> sticker;
		vector<vector<int>> memo(2, vector<int>(N, 0));
		
		for (j = 0; j < 2; j++) {
			vector<int> tmp;
			for (i = 0; i < N; i++)
			{
				num_tmp;
				cin >> num_tmp;
				tmp.push_back(num_tmp);
			}
			sticker.push_back(tmp);
		}

		for (i = 0; i < N; i++)
		{
			memo[0][i] = sticker[0][i];
			memo[1][i] = sticker[1][i];
			if (i == 0) {}
			else if (i == 1) {
				memo[0][i] += memo[1][i - 1];
				memo[1][i] += memo[0][i - 1];
			}
			else {
				memo[0][i] += max(memo[1][i - 1], memo[1][i - 2]);
				memo[1][i] += max(memo[0][i - 1], memo[0][i - 2]);
			}
		}
		cout << max(memo[0][N - 1], memo[1][N - 1]) << endl;
	}
	return 0;
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define max(x, y) ((x > y) ? x : y)
int s[2][100000] = { 0, };
int main() {
	int T, N, t, i, j;
	scanf("%d", &T);
	for (t = 0; t < T; t++)
	{
		int m[2][100002] = { 0, };
		scanf("%d", &N);

		for (j = 0; j < 2; j++) {
			for (i = 0; i < N; i++)
			{
				scanf("%d", &s[j][i]);
			}
		}


		for (i = 0; i < N; i++)
		{
			m[0][i] += s[0][i];
			m[1][i] += s[1][i];

			m[0][i + 1] = max(m[1][i], m[0][i + 1]);
			m[0][i + 2] = max(m[1][i], m[0][i + 2]);
			m[1][i + 1] = max(m[0][i], m[1][i + 1]);
			m[1][i + 2] = max(m[0][i], m[1][i + 2]);
		}
		printf("%d\n", max(m[0][N - 1], m[1][N - 1]));
	}
	return 0;
}