๐ Coding Test Study/Algorithm Problem
[C++][BAEKJOON][DP] 9456๋ฒ ์คํฐ์ปค
ibelieveinme
2021. 8. 22. 17:04
728x90
๋ฌธ์
https://www.acmicpc.net/problem/9465
9465๋ฒ: ์คํฐ์ปค
์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ n (1 ≤ n ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ ๋ ์ค์๋ n๊ฐ์ ์ ์๊ฐ ์ฃผ์ด์ง๋ฉฐ, ๊ฐ ์ ์๋ ๊ทธ ์์น์ ํด๋นํ๋ ์คํฐ์ปค์
www.acmicpc.net
๋ฌธ์ ์ค๋ช
์ฝ๋
#include <iostream>
#include <algorithm>
using namespace std;
int sticker[2][100001];
int searchMaxScore(int);
int main() {
int testcase = 0;
cin >> testcase;
for (int t = 0; t < testcase; t++) {
int column = 0;
cin >> column;
for (int row = 0; row < 2; row++) {
for (int col = 1; col <= column; col++) {//๋ฐ๋ณต๋ฌธ์ index 2๋ถํฐ ์์ํ๊ธฐ ์ํด
cin >> sticker[row][col];
}
}
cout << searchMaxScore(column) << "\n";
}
}
int searchMaxScore(int column) {
for (int i = 2; i <= column; i++) {
//์ ์คํฐ์ปค์ ๊ฒฝ์ฐ์ ์
sticker[0][i] += max(sticker[1][i - 1], sticker[1][i - 2]);
//์๋ ์คํฐ์ปค์ ๊ฒฝ์ฐ์ ์
sticker[1][i] += max(sticker[0][i - 1], sticker[0][i - 2]);
}
return max(sticker[0][column], sticker[1][column]);
}
728x90