[백준] 알고리즘 13301번 - 타일 장식물 문제

문제

www.acmicpc.net/problem/13301

13301번: 타일 장식물

소스코드

#include <bits/stdc++.h>
using namespace std;
long long dp[81];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	cin >> n;
	dp[0] = 1, dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + dp[i - 2];
	}
	long long ans = 0;
	ans = dp[n] * 2 + dp[n - 1] * 2;
	cout << ans;
}

풀이

예시에서 보듯이 타일의 숫자가 늘어나는건 피보나치임을 직감할 수 있다.

또한 5, 6 의 출력물로 보았을 때 직사각형의 넓이는 현재n의 dp와 그 이전의 dp값에 저장된 길이가 전체 직사각형들의 각각의 변임을 알 수 있다.

 

즉 둘레는 각각의변을 전부다 더해주면된다.