๐๋ฌธ์ ๋ณด๋ฌ๊ฐ๊ธฐ
๐ง๐ป๐ปํ์ด ๊ณผ์
N์๋ฆฌ ์ซ์์์ ์ผ์ ์๋ฆฌ๊ฐ 0 ~ 9๋ก ๋๋๋ ๊ณ๋จ ์๋ค์ ๊ฐ์๋ฅผ ์์๋ด ์๋ค. ๋จผ์ , \( N = 1\)์ผ ๋๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
[ N = 1 ์ผ ๋ ]
i = 0 | i = 1 | i = 2 | i = 3 | i = 4 | i = 5 | i = 6 | i = 7 | i = 8 | i = 9 |
0 | 1 |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
[ N = 2 ์ผ ๋ ]
i = 0 | i = 1 | i = 2 | i = 3 | i = 4 | i = 5 | i = 6 | i = 7 | i = 8 | i = 9 |
1 | 1 | 2 | 2 | 2 | 2 | 2 | 2 | 2 | 1 |
[ N = 3 ์ผ ๋ ]
i = 0 | i = 1 | i = 2 | i = 3 | i = 4 | i = 5 | i = 6 | i = 7 | i = 8 | i = 9 |
1 | 3 | 3 | 4 | 4 | 4 | 4 | 4 | 3 | 2 |
์ด ์ ๋๊น์ง ์งํํด๋ณด๋, ๊ท์น์ฑ์ด ๋ณด์ด๊ธฐ ์์ํฉ๋๋ค.
N ์๋ฆฌ ์ซ์์์ i ์ซ์๋ก ๋๋๋ ๊ณ๋จ ์์ ๊ฐ์๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด์ dp[N][i]๋ผ๊ณ ํ๋ค๋ฉด, ๊ท์น์ฑ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
dp[N][0] = dp[N-1][1]
dp[N][i] = dp[N-1][i-1] + dp[N-1][i+1]; (i > 0 and i < 9)
dp[N][9] = dp[N-1][8]
์ฆ, ๋์ ํ๋ก๊ทธ๋๋ฐ์ ์ด์ฉํ์ฌ N = 1์ผ ๋์ i๊ฐ๋ค์ ๋ฐํ์ผ๋ก N = 2, N = 3์ ๊ฐ๋ค์ ์ฐจ๋ก๋๋ก ์์๋ผ ์ ์์ต๋๋ค.
๋ํ, ๋์ ํ๋ก๊ทธ๋๋ฐ์ ์ฌ์ฉํ ๋ฐฐ์ด์ \( 2 \times 10 \) ํฌ๊ธฐ๋ง ๊ฐ์ง๋ค๋ฉด, ๋ชจ๋ N์ ๋ํ ๊ณ๋จ ์ ๊ฐ์๋ฅผ ์์๋ผ ์ ์์ต๋๋ค.
์ด๊ฒ์ด ์ด๋ป๊ฒ ๊ฐ๋ฅํ ๊น์? ์ ๋ ๋ค์๊ณผ ๊ฐ์ ๋ฐฉ๋ฒ์ผ๋ก ๊ตฌํํ ์ ์์์ต๋๋ค.
๋จผ์ , ํ์ ๊ฐ๋ฆฌํค๋ ๋ณ์๋ฅผ ๋ค์๊ณผ ๊ฐ์ด 2๊ฐ ์ ์ธํฉ๋๋ค.
int writeBufferIndex = 0, readBufferIndex = 1;
- writeBufferIndex๋ readBufferIndex์ ํ์์ ์ฝ์ด์ ์๋ก ๊ฐ์ ์ฐ๊ฒ ๋๋ ํ์ ์๋ฏธํฉ๋๋ค.
- ์์์ ๋ง๋ค์๋ ์ ํ์์ ๋น์ ํ์๋ฉด, writeBufferIndex๋ N, readBufferIndex๋ N - 1์ ํด๋นํ๋ค๊ณ ๋ณผ ์ ์์ต๋๋ค.
- ํ ํ์ ๋ํ์ฌ ๋ชจ๋ ์ฐ์ฐ์ด ๋๋ฌ๋ค๋ฉด, writeBufferIndex์ readBufferIndex๊ฐ ์๋ก ๊ฐ์ ๊ตํํจ์ผ๋ก์จ, ์ญํ ์ ๋ฐ๊ฟ์ ๋ค์ ์ฐ์ฐ์ ์ด์ด๋๊ฐ๊ฒ ๋ฉ๋๋ค.
N์ด ํด์๋ก 2์ฐจ์ ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ ์ปค์ง๊ฒ ๋์ด ๋ฉ๋ชจ๋ฆฌ๋ฅผ ๋ง์ด ์ฐ๊ฒ ๋ฉ๋๋ค. ์ ๋ ์ ์ ํ์์ ๋์ถํ๋ ๊ณผ์ ์์ ํ์ด N๊ฐ๊น์ง ํ์ ์์ ๊ฒ ๊ฐ๋ค๋ ์๊ฐ์ด ๋ค์๊ณ , ๊ทธ๋ํฝ์ค ๋ ๋๋ง์์ ์ฌ์ฉ๋๋ ๋๋ธ ๋ฒํผ๋ง(Double Buffering) ๊ธฐ๋ฒ์์ ์์ด๋์ด๋ฅผ ์ป์ด, ์์ ๊ฐ์ด ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌ์ฑํ๊ฒ ๋์์ต๋๋ค.
โ๏ธ์์ค ์ฝ๋ ๋ฐ ๊ฒฐ๊ณผ
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000000;
const int DIGIT_COUNT = 10;
const int BUFFER_COUNT = 2;
void Swap(int& x, int& y)
{
int temp = x;
x = y;
y = temp;
}
int main()
{
ios::sync_with_stdio(false);
cout.tie(NULL); cin.tie(NULL);
int N;
cin >> N;
// 1. ์ด๊ธฐํ
vector<vector<int>> dp(BUFFER_COUNT, vector<int>(DIGIT_COUNT));
int writeBufferIndex = 0, readBufferIndex = 1;
int sum = 9;
for (int i = 1; i < DIGIT_COUNT; i++)
dp[writeBufferIndex][i] = 1;
// ------------------------------------
// 2. ๋ก์ง
Swap(writeBufferIndex, readBufferIndex);
for (int i = 1; i < N; i++)
{
sum = 0;
for (int j = 0; j < DIGIT_COUNT; j++)
{
if (j == 0 or j == 9)
{
int targetIndex = (j == 0) ? j + 1 : j - 1;
int newValue = dp[readBufferIndex][targetIndex];
dp[writeBufferIndex][j] = newValue;
sum = (sum + newValue) % MOD;
continue;
}
dp[writeBufferIndex][j] = (dp[readBufferIndex][j - 1] + dp[readBufferIndex][j + 1]) % MOD;
sum = (sum + dp[writeBufferIndex][j]) % MOD;
}
Swap(writeBufferIndex, readBufferIndex);
}
cout << sum;
return 0;
}
'๐คAlgorithm > BOJ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[BOJ] 16139๋ฒ | ์ธ๊ฐ-์ปดํจํฐ ์ํธ์์ฉ (C++) (1) | 2023.08.27 |
---|---|
[BOJ] 11659๋ฒ | ๊ตฌ๊ฐ ํฉ ๊ตฌํ๊ธฐ 4 (C++) (0) | 2023.08.27 |
[BOJ] 3190๋ฒ | ๋ฑ (C++) (1) | 2023.08.26 |
[BOJ] 16198๋ฒ | ์๋์ง ๋ชจ์ผ๊ธฐ (C++) (0) | 2023.08.25 |
[BOJ] 1759๋ฒ | ์ํธ ๋ง๋ค๊ธฐ (C++) (0) | 2023.08.25 |