백준 9465 c++ "스티커" -PlusUltraCode-

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

 

 

[필자 사고]

동적 프로그래밍 문제이다.

필자는 해당 dp점화식을 다음과 같이 설계했다.

dp[i][k] = buf[i][k] + 이전 dp값들

즉 현재 위치는 반드시 값이 들어가야 되고 이전 dp의 최대값들을 갱신하는 형태로 설계를 했따.

[코드 해설]

2. 입력 처리 (Init 함수)

Init() 함수는 입력을 받아서 점수 배열과 DP 배열을 초기화하는 역할을 합니다.

1. buf (입력된 점수 저장)와 dp (최대 점수 저장) 벡터를 초기화합니다.
2. buf는 두 개의 행과 N개의 열을 가지므로, buf[0]과 buf[1]에 점수를 저장합니다.
3. dp 배열을 이용하여 초기 조건을 설정합니다.
   • 첫 번째 열(dp[0][0], dp[1][0])은 buf[0][0], buf[1][0]과 같습니다.
   • 두 번째 열(dp[0][1], dp[1][1])은 첫 번째 열의 반대편 값을 더한 값으로 설정합니다.

---

3. 최대 점수 계산 (Game_Start 함수)

Game_Start() 함수는 점수를 최대로 만들 수 있는 값을 DP 방식으로 계산합니다.

1. dp[0][i]는 buf[0][i]에 dp[1][i-1] 또는 dp[1][i-2] 중 더 큰 값을 더한 값으로 설정합니다.
2. dp[1][i]는 buf[1][i]에 dp[0][i-1] 또는 dp[0][i-2] 중 더 큰 값을 더한 값으로 설정합니다.
3. 마지막 열(N-1)까지 계산한 후, dp[0][N-1]과 dp[1][N-1] 중 큰 값을 출력합니다

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int T;
int N;
vector<vector<int>> buf;
vector<vector<int>> dp;


void Init() {
	buf.clear();
	dp.clear();

	buf.resize(2);
	dp.resize(2);

	for (int i = 0; i < 2; i++) {
		buf[i].resize(N);
		dp[i].resize(N);
	}
	for (int i = 0; i < N; i++) {
		cin >> buf[0][i];
	}
	for (int i = 0; i < N; i++) {
		cin >> buf[1][i];
	}

	dp[0][0] = buf[0][0];
	dp[1][0] = buf[1][0];
	dp[0][1] = buf[0][1] + dp[1][0];
	dp[1][1] = buf[1][1] + dp[0][0];

}

void Game_Start() {
	cin >> N;

	Init();
	for (int i = 2; i < N; i++) {
		dp[0][i] = buf[0][i] + max(dp[1][i - 1], dp[1][i - 2]);
		dp[1][i] = buf[1][i] + max(dp[0][i - 1], dp[0][i - 2]);
	}

	cout << max(dp[0][N - 1], dp[1][N - 1]) << '\n';
}

int main(void) {
	cin >> T;
	while (T--) {
		Game_Start();
	}
}