๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ“ ์•Œ๊ณ ๋ฆฌ์ฆ˜/BOJ

[C++/BOJ] 9465 : ์Šคํ‹ฐ์ปค (DP)

728x90

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;
}

 

728x90