Algorithm/Baekjoon
[Algorithm]Baekjoon 13301번 :: 타일 장식물
MaxLevel
2024. 1. 10. 19:35
https://www.acmicpc.net/problem/13301
13301번: 타일 장식물
대구 달성공원에 놀러 온 지수는 최근에 새로 만든 타일 장식물을 보게 되었다. 타일 장식물은 정사각형 타일을 붙여 만든 형태였는데, 한 변이 1인 정사각형 타일부터 시작하여 마치 앵무조개
www.acmicpc.net
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
int n;
long long dp[81] = { 0 };
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
dp[1] = dp[2] = 1;
cin >> n;
for (int i = 3; i <= n; ++i)
{
dp[i] = dp[i - 1] + dp[i - 2];
}
cout << 2 * (dp[n] + dp[n - 1]) + 2 * dp[n];
}
|
cs |
문제에서의 도형이 구성되는 원리는, 피보나치수열의 공식으로 이루어져 있다.
그리고 최종적으로 구성되는 직사각형을 보면 가로,세로중 둘 중 하나는 dp[i] - dp[i-1]값으로 되어있고 나머지 하나는 dp[i]이기 때문에, 각각 2를 곱해서 더해주면 둘레길이를 알 수 있다.