hades

[Baekjoon] 11726๋ฒˆ: 2xn ํƒ€์ผ๋ง ๋ณธ๋ฌธ

๐Ÿ‘Š PS/Algorithm

[Baekjoon] 11726๋ฒˆ: 2xn ํƒ€์ผ๋ง

hades1 2024. 7. 26. 11:05

๐Ÿฅ… ๋ฌธ์ œ

https://www.acmicpc.net/problem/11726

 

๐Ÿ” ์„ค๊ณ„

์ง์ ‘ ๊ทธ๋ ค์„œ ํŒŒ์•…ํ•ด๋ณด๋ฉด, ํŒŒ๋ž€์ƒ‰ ํ™”์‚ดํ‘œ๋Š” 2*1 ํƒ€์ผ์„ ์ถ”๊ฐ€ํ•˜์—ฌ ๋งŒ๋“ค์–ด์ง€๊ณ , ๋นจ๊ฐ„์ƒ‰ ํ™”์‚ดํ‘œ๋Š” 1*2 ํƒ€์ผ์„ ๋‘ ๊ฐœ ๋ถ™์ธ ๊ฒƒ์„ ์ถ”๊ฐ€ํ•˜์—ฌ ๋งŒ๋“ค์–ด์ง„๋‹ค.

 

์ฆ‰, dp[i] = dp[i-1] + dp[i-2]๋ผ๋Š” ๊ฒƒ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค.

 

๐Ÿ‘Š ํ’€์ด

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

int n;
vector<int> dp(1001);

int main(void)
{	
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	dp[1] = 1;
	dp[2] = 2;
	for (int i = 3; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
		dp[i] %= 10007;
	}
	cout << dp[n] << "\n";
	return 0;
}