https://www.acmicpc.net/problem/9465
[필자 사고]
동적 프로그래밍 문제이다.
필자는 해당 dp점화식을 다음과 같이 설계했다.
dp[i][k] = buf[i][k] + 이전 dp값들
즉 현재 위치는 반드시 값이 들어가야 되고 이전 dp의 최대값들을 갱신하는 형태로 설계를 했따.
[코드 해설]
2. 입력 처리 (Init 함수)
Init() 함수는 입력을 받아서 점수 배열과 DP 배열을 초기화하는 역할을 합니다.
- buf (입력된 점수 저장)와 dp (최대 점수 저장) 벡터를 초기화합니다.
- buf는 두 개의 행과 N개의 열을 가지므로, buf[0]과 buf[1]에 점수를 저장합니다.
- 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 방식으로 계산합니다.
- dp[0][i]는 buf[0][i]에 dp[1][i-1] 또는 dp[1][i-2] 중 더 큰 값을 더한 값으로 설정합니다.
- dp[1][i]는 buf[1][i]에 dp[0][i-1] 또는 dp[0][i-2] 중 더 큰 값을 더한 값으로 설정합니다.
- 마지막 열(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();
}
}
'백준 > 동적프로그래밍' 카테고리의 다른 글
백준 14916 c++ "거스름돈" -PlusUltraCode- (0) | 2025.02.07 |
---|---|
백준 9655 c++ "돌 게임" -PlusUltraCode- (0) | 2025.02.06 |
백준 1562 c++ "계단 수" -PlusUltraCode- (0) | 2024.12.26 |
백준 c++ 1904 "01타일" -PlusUltraCode- (0) | 2024.05.10 |
백준 12865 c++ "평범한 배낭" -PlusUltraCode- (0) | 2024.05.09 |