๐ฃ ๋ฌธ์ ์ดํด
์์ ํ์๋ 2193๋ฒ ์ด์น์ ์ ์๋นํ ๋น์ทํ ๋ฌธ์ ์ด๋ค.
1. 0 ๊ณผ 1 ๋ก ์ด์ง์๋ฅผ ๋ง๋ค๊ณ ์ ํ๋ค.
2. 0 ์ ๋ฌด์กฐ๊ฑด 00 ํํ๋ก๋ง ์ฐ์ด๊ณ 1 ์ ์ํ๋ ๋๋ก ์ธ ์ ์๋ค.
3. ์ ๋ ฅ์ผ๋ก ์ฃผ์ด์ง N ์๋ฆฌ ์์ ์ด์ง์๋ฅผ ์ด ๋ช ๊ฐ์ง ๋ง๋ค ์ ์๋์ง ๊ตฌํ๋ฉด ๋๋ค.
4. !! ์ฐพ์ ์์ด์ ๊ฐ์๋ฅผ 15746 ์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ถ๋ ฅํด์ผ ํ๋ค !!
๋์ ๊ณํ๋ฒ(Dynamic Programming) ๋ฐฉ์์ ์ฌ์ฉํ๋ค.
๐ญ ํ์ด ๊ณผ์
N = 1 ์ธ ๊ฒฝ์ฐ 1 ๋ก ์ด 1๊ฐ์ง
N = 2 ์ธ ๊ฒฝ์ฐ 11, 00 ์ผ๋ก ์ด 2๊ฐ์ง
N = 3 ์ธ ๊ฒฝ์ฐ 111, 100, 001 ์ผ๋ก ์ด 3๊ฐ์ง
N = 4 ์ธ ๊ฒฝ์ฐ 1111, 1001, 1100, 0011, 0000 ์ผ๋ก ์ด 5๊ฐ์ง
N = 5 ์ธ ๊ฒฝ์ฐ 11111, 11100, 10011, 11001, 00111, 00100, 10000, 00001 ์ผ๋ก ์ด 8๊ฐ์ง
๊ฒฝ์ฐ์ ์๊ฐ ํผ๋ณด๋์น ์์ด๋ก ๋ณํ๋ ๊ฒ์ ์ฐพ์ ์ ์์๋ค.
์์ฑ ์ธ์ด: C++
#include <cstdio>
int dp[1000010] = {0, };
void solve(int num){
dp[1] = 1; dp[2] = 2;
for (int i = 3; i <= num; ++i) {
// ๊ฐ์ด ์ง๋์น๊ฒ ํฐ ๊ฒฝ์ฐ๋ฅผ ๋๋นํด์ 15746์ผ๋ก ๋๋ ๋๋จธ์ง๋ฅผ ์ ์ฅ
dp[i] = ( dp[i-2] + dp[i-1] ) % 15746;
}
}
int main(){
int nLength;
scanf("%d", &nLength);
solve(nLength);
printf("%d\n", dp[nLength]);
return 0;
}
๐ ๋ฐฐ์ด ์
๋ฐ๋ก ์์ ํ์ด๋ณธ ๋ฌธ์ ์ ์ ํ์ด ์ ์ฌํด์ ๋ฌด๋ํ๊ฒ ํ์๋ ๋ฌธ์ ์ด๋ค.