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
'๐ ์๊ณ ๋ฆฌ์ฆ > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[C++/BOJ] 7562 : ๋์ดํธ์ ์ด๋ (BFS) (0) | 2023.03.02 |
---|---|
[C++/BOJ] 1309 : ๋๋ฌผ์ (DP) (0) | 2023.02.23 |
[C++/BOJ] 1697 : ์จ๋ฐ๊ผญ์ง (BFS) (0) | 2023.02.23 |
[C++/BOJ] 14940 : ์ฌ์ด ์ต๋จ๊ฑฐ๋ฆฌ (BFS) / test case (0) | 2023.02.22 |
[C++/BOJ] 2149 : ์ํธ ํด๋ (0) | 2023.02.22 |