https://www.acmicpc.net/problem/9465
๋ฌธ์
์๊ทผ์ด์ ์ฌ๋์ ์๋ฅ์ด๋ ๋ฌธ๋ฐฉ๊ตฌ์์ ์คํฐ์ปค 2n๊ฐ๋ฅผ ๊ตฌ๋งคํ๋ค. ์คํฐ์ปค๋ ๊ทธ๋ฆผ (a)์ ๊ฐ์ด 2ํ n์ด๋ก ๋ฐฐ์น๋์ด ์๋ค. ์๋ฅ์ด๋ ์คํฐ์ปค๋ฅผ ์ด์ฉํด ์ฑ ์์ ๊พธ๋ฏธ๋ ค๊ณ ํ๋ค.
์๋ฅ์ด๊ฐ ๊ตฌ๋งคํ ์คํฐ์ปค์ ํ์ง์ ๋งค์ฐ ์ข์ง ์๋ค. ์คํฐ์ปค ํ ์ฅ์ ๋ผ๋ฉด, ๊ทธ ์คํฐ์ปค์ ๋ณ์ ๊ณต์ ํ๋ ์คํฐ์ปค๋ ๋ชจ๋ ์ฐข์ด์ ธ์ ์ฌ์ฉํ ์ ์๊ฒ ๋๋ค. ์ฆ, ๋ ์คํฐ์ปค์ ์ผ์ชฝ, ์ค๋ฅธ์ชฝ, ์, ์๋์ ์๋ ์คํฐ์ปค๋ ์ฌ์ฉํ ์ ์๊ฒ ๋๋ค.
๋ชจ๋ ์คํฐ์ปค๋ฅผ ๋ถ์ผ ์ ์๊ฒ๋ ์๋ฅ์ด๋ ๊ฐ ์คํฐ์ปค์ ์ ์๋ฅผ ๋งค๊ธฐ๊ณ , ์ ์์ ํฉ์ด ์ต๋๊ฐ ๋๊ฒ ์คํฐ์ปค๋ฅผ ๋ผ์ด๋ด๋ ค๊ณ ํ๋ค. ๋จผ์ , ๊ทธ๋ฆผ (b)์ ๊ฐ์ด ๊ฐ ์คํฐ์ปค์ ์ ์๋ฅผ ๋งค๊ฒผ๋ค. ์๋ฅ์ด๊ฐ ๋ ์ ์๋ ์คํฐ์ปค์ ์ ์์ ์ต๋๊ฐ์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค. ์ฆ, 2n๊ฐ์ ์คํฐ์ปค ์ค์์ ์ ์์ ํฉ์ด ์ต๋๊ฐ ๋๋ฉด์ ์๋ก ๋ณ์ ๊ณต์ ํ์ง ์๋ ์คํฐ์ปค ์งํฉ์ ๊ตฌํด์ผ ํ๋ค.
์์ ๊ทธ๋ฆผ์ ๊ฒฝ์ฐ์ ์ ์๊ฐ 50, 50, 100, 60์ธ ์คํฐ์ปค๋ฅผ ๊ณ ๋ฅด๋ฉด, ์ ์๋ 260์ด ๋๊ณ ์ด ๊ฒ์ด ์ต๋ ์ ์์ด๋ค. ๊ฐ์ฅ ๋์ ์ ์๋ฅผ ๊ฐ์ง๋ ๋ ์คํฐ์ปค (100๊ณผ 70)์ ๋ณ์ ๊ณต์ ํ๊ธฐ ๋๋ฌธ์, ๋์์ ๋ ์ ์๋ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค์ ์ฒซ์งธ ์ค์๋ n (1 ≤ n ≤ 100,000)์ด ์ฃผ์ด์ง๋ค. ๋ค์ ๋ ์ค์๋ n๊ฐ์ ์ ์๊ฐ ์ฃผ์ด์ง๋ฉฐ, ๊ฐ ์ ์๋ ๊ทธ ์์น์ ํด๋นํ๋ ์คํฐ์ปค์ ์ ์์ด๋ค. ์ฐ์ํ๋ ๋ ์ ์ ์ฌ์ด์๋ ๋น ์นธ์ด ํ๋ ์๋ค. ์ ์๋ 0๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ๊ณ , 100๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์ ์์ด๋ค.
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค ๋ง๋ค, 2n๊ฐ์ ์คํฐ์ปค ์ค์์ ๋ ๋ณ์ ๊ณต์ ํ์ง ์๋ ์คํฐ์ปค ์ ์์ ์ต๋๊ฐ์ ์ถ๋ ฅํ๋ค.
์ค๋ฒ1
dp ๋ฌธ์ ์ด๋ค!
์ฒ์์ ์๋์ฒ๋ผ ํ์๋ค๊ฐ ๋ต์ด ํ๋ฆฌ๊ฒ ๋์ค๊ธธ๋ ๋ญ๊ฐ ๋ฌธ์ ์ธ๊ฐ ํ๋๋ฐ,,
stick[0][k] += max(stick[1][k - 1], stick[0][k - 2]);
stick[1][k] += max(stick[0][k - 1], stick[1][k - 2]);
์ ์์์ stick[0][k - 2] ์ ์ด๋ฏธ ๊ทธ ๋๊ฐ์ ์ธ stick[1][k - 1] ์ ๊ตฌํ ๋ ๊ณ์ฐํ์ผ๋ฏ๋ก,
stick[1][k - 1] ๊ณผ stick[0][k - 2] ์ ๋น๊ตํ๋ ๋์
์๋์ฒ๋ผ stick[1][k - 1] ๊ณผ stick[1][k - 2] ๋ฅผ ๋ฃ๋๊ฒ ์ฌ๋ฐ๋ฅธ ์ ํ์์ด์๋ค.
stick[0][k] += max(stick[1][k - 1], stick[1][k - 2]);
stick[1][k] += max(stick[0][k - 1], stick[0][k - 2]);
๋์ ํ์ด
#include <iostream>
using namespace std;
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int t = 0;
int n = 0;
cin >> t;
for (int i = 0; i < t; ++i){
cin >> n;
int stick[2][100001] = {{0}};
for (int j = 0; j < n; ++j){
cin >> stick[0][j];
}
for (int j = 0; j < n; ++j){
cin >> stick[1][j];
}
// cout << stick[0][0] << " " << stick[1][0] << "\n";
for (int k = 1; k < n; ++k){
if(k==1){
stick[0][k] += stick[1][k - 1];
stick[1][k] += stick[0][k - 1];
// cout << stick[0][k] << " " << stick[1][k] << "\n";
continue;
}
stick[0][k] += max(stick[1][k - 1], stick[1][k - 2]);
stick[1][k] += max(stick[0][k - 1], stick[0][k - 2]);
// cout << stick[0][k] << " " << stick[1][k] << "\n";
}
cout << max(stick[0][n - 1], stick[1][n - 1])<<"\n";
}
return 0;
}
'๐ ์๊ณ ๋ฆฌ์ฆ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/BOJ] 1890 : ์ ํ (DP) (1) | 2023.03.16 |
---|---|
[C++/BOJ] 9251 : LCS (DP) (0) | 2023.03.16 |
[C++/BOJ] 10971 : ์ธํ์ ์ํ 2 (์์ ํ์, dfs, Backtracking) (0) | 2023.03.06 |
[C++/BOJ] 9663 : N-Queen (์์ ํ์, Backtracking) (0) | 2023.03.06 |
[C++/BOJ] 1158 : ์์ธํธ์ค ๋ฌธ์ (Queue) (0) | 2023.03.03 |