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

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

[C++/BOJ] 2225 : ํ•ฉ๋ถ„ํ•ด (DP)

728x90

๋ฌธ์ œ

0๋ถ€ํ„ฐ N๊นŒ์ง€์˜ ์ •์ˆ˜ K๊ฐœ๋ฅผ ๋”ํ•ด์„œ ๊ทธ ํ•ฉ์ด N์ด ๋˜๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜๋ฅผ ๊ตฌํ•˜๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์‹œ์˜ค.

๋ง์…ˆ์˜ ์ˆœ์„œ๊ฐ€ ๋ฐ”๋€ ๊ฒฝ์šฐ๋Š” ๋‹ค๋ฅธ ๊ฒฝ์šฐ๋กœ ์„ผ๋‹ค(1+2์™€ 2+1์€ ์„œ๋กœ ๋‹ค๋ฅธ ๊ฒฝ์šฐ). ๋˜ํ•œ ํ•œ ๊ฐœ์˜ ์ˆ˜๋ฅผ ์—ฌ๋Ÿฌ ๋ฒˆ ์“ธ ์ˆ˜๋„ ์žˆ๋‹ค.

์ž…๋ ฅ

์ฒซ์งธ ์ค„์— ๋‘ ์ •์ˆ˜ N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)๊ฐ€ ์ฃผ์–ด์ง„๋‹ค.

์ถœ๋ ฅ

์ฒซ์งธ ์ค„์— ๋‹ต์„ 1,000,000,000์œผ๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.

 


 

๋ฐฑ์ค€ ๊ณจ๋“œ5.

์ข€ ์–ด๋ ค์šด dp๋ฌธ์ œ

์ ํ™”์‹ ์•Œ์•„๋‚ด๊ธฐ ์‹œ์ž‘

 

์ ํ™”์‹์„ ๋‚ด๋†”๋ผ...

๊ตฌ๊ธ€๋งํ•ด๋ณด๋‹ˆ ์›๋ž˜ ๋‹ค๋ฅธ ์ ํ™”์‹์ด ์žˆ๋Š”๋ฐ,

๋‚ด๊ฐ€ ๊ตฌํ•œ๊ฑด ์•ฝ๊ฐ„ ๊ผผ์ˆ˜(?) ๋ฒ„์ „์ธ๋“ฏ.

๊ทธ๋ƒฅ n๊ณผ k๋ฅผ ๋Œ€์ž…ํ•ด๋ณด๋ฉด์„œ ์•Œ์•„๋ƒˆ๋‹ค.

 

dp[n][k] = dp[n-1][k] + dp[n][k-1]

 

 

 

 

๋‚˜์˜ ํ’€์ด

#include <iostream>
#include <queue>
using namespace std;

int main(){
    int n;
    int k;
    cin >> n >> k;
    int dp[202][202] = {0,};
    dp[1][1] = 1; // dp[n][k]
    for (int i = 2; i <= n; ++i) dp[i][1] = 1;
    for (int i = 2; i <= k; ++i) dp[1][i] = i;

    for (int i = 2; i <= n; ++i){
        for (int j = 2; j <= k; ++j){
            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
        }
    }
    cout << dp[n][k];
}

 

728x90