[BOJ] 2xn ํƒ€์ผ๋ง(11726)

[๋ฐฑ์ค€(BOJ)] 2xn ํƒ€์ผ๋ง(11726) C++

๋ฌธ์ œ : BOJ_11726๋ฒˆ 2xn ํƒ€์ผ๋ง

๋ฌธ์ œ ์„ค๋ช…

DP

DP๋ฅผ ํ™œ์šฉํ•˜์—ฌ ํ•ด๊ฒฐํ•  ์ˆ˜ ์žˆ๋Š” ๊ธฐ๋ณธ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
2X1, 1X2 ํฌ๊ธฐ์˜ ๋ธ”๋ก์ด ์žˆ๊ณ , n์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.
์ด๋•Œ 2Xn ํฌ๊ธฐ์˜ ์ง์‚ฌ๊ฐํ˜•์„ ๋ธ”๋ก์„ ์ด์šฉํ•ด ์ฑ„์šฐ๋Š” ๋ฐฉ๋ฒ•์˜ ์ˆ˜๋ฅผ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค
๋ฐฉ๋ฒ•์˜ ์ˆ˜๊ฐ€ ์ปค์ง€๋ฏ€๋กœ 10,007๋กœ ๋‚˜๋ˆˆ ๋‚˜๋จธ์ง€๋ฅผ ์ถœ๋ ฅํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.


Solution

n์˜ ํฌ๊ธฐ๊ฐ€ 1์ด๋ผ๋ฉด, 1X2 ์˜ ๋ธ”๋ก ํ•˜๋‚˜๋ฅผ ์„ธ์šฐ๋Š” 1๊ฐ€์ง€ ๊ฒฝ์šฐ์˜ ์ˆ˜ ๋ฐ–์— ์—†์Šต๋‹ˆ๋‹ค.
n์˜ ํฌ๊ธฐ๊ฐ€ 2๋ผ๋ฉด, 1X2 ์˜ ๋ธ”๋ก ๋‘ ๊ฐœ๋ฅผ ์„ธ์šฐ๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜, 2X1 ์˜ ๋ธ”๋ก ๋‘ ๊ฐœ๋ฅผ ์Œ“๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜, ์ด 2๊ฐœ์ž…๋‹ˆ๋‹ค.
n์˜ ํฌ๊ธฐ๊ฐ€ 3 ์ด์ƒ ์ผ ๋•Œ, DP๋ฅผ ์ ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ๊ทœ์น™์ด ์žˆ์Šต๋‹ˆ๋‹ค.

๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ n ๋ฒˆ ์งธ ์นธ์— 1X2 ์˜ ๋ธ”๋ก ํ•˜๋‚˜๋ฅผ ์„ธ์šด๋‹ค๋ฉด, ๊ทธ ์˜†์— n-1์นธ์€ n-1๊ฐœ์˜ ๋ธ”๋ก์„ ์„ธ์›Œ๋‘๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.
๊ฐ€์žฅ ์˜ค๋ฅธ์ชฝ n ๋ฒˆ ์งธ์™€ n-1 ๋ฒˆ ์งธ ์นธ์— 2X1 ์˜ ๋ธ”๋ก ๋‘ ๊ฐœ๋ฅผ ์Œ“๋Š”๋‹ค๋ฉด, ๊ทธ ์˜†์— n-2์นธ์€ n-2๊ฐœ์˜ ๋ธ”๋ก์„ ์„ธ์›Œ๋‘๋Š” ๊ฒฝ์šฐ์˜ ์ˆ˜์™€ ๊ฐ™์Šต๋‹ˆ๋‹ค.
๊ทธ๋Ÿฌ๋ฏ€๋กœ dp[n] = dp[n-1] + dp[n-2] ์ด ์„ฑ๋ฆฝํ•จ์„ ์•Œ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


Description

  • dp์˜ ๊ฐ’์„ ๋ฐ›๋Š” ๋ฐฐ์—ด์€ vector๋กœ ๋™์ ํ• ๋‹นํ•˜์˜€์Šต๋‹ˆ๋‹ค.
  • resize๋œ vector์— ๊ฐ’์ด ๋“ค์–ด์™€์žˆ๋‹ค๋ฉด, ์žฌ๊ท€๊ฐ€ ๋“ค์–ด๊ฐ€์ง€ ์•Š๊ณ  return ํ•จ์œผ๋กœ์จ, ๋ฉ”๋ชจ์ด์ œ์ด์…˜์„ ํ–ˆ์Šต๋‹ˆ๋‹ค.
  • #define MOD 10007;๋กœ mod ์—ฐ์‚ฐ์„ ํ•ด์•ผ ํ•  ์ˆ˜๋ฅผ ์ •์˜ํ–ˆ์Šต๋‹ˆ๋‹ค.

#include <iostream>
#include <vector>
#define MOD 10007;
using namespace std;
vector<long long> arr;
long long dp(int n);
int main(void) {
	int n;
	cin >> n;
	arr.resize(n + 1);
	cout << dp(n) << '\n';
}
long long dp(int n) {
	if (n == 1) return arr[n] = 1;
	else if (n == 2) return arr[n] = 2;
	if (arr[n] != 0) return arr[n];
	return arr[n] = (dp(n - 1) + dp(n - 2))%MOD;
}