C++ / 13301 / 타일 장식물 ( 다이나믹 프로그래밍 )

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

문제 요약

그림에서 타일에 적힌 수는 각 타일의 한 변의 길이를 나타냅니다. 타일 장식물을 구성하는 정사각형 타일 한 변의 길이를 안쪽 타일부터 시작하여 차례로 적으면다음과 같습니다.

1, 1, 2, 3, 5, 8 ...

타일의 개수n이 주어졌을 때, n개의 타일로 구성된 직사각형의 툴레를 구해야합니다.

문제 풀이

1. 타일 개수를 입력받습니다.

2. dp 함수를 만듭니다. 안에서는 기본 피보나치 배열을 만듬과 동시에 정답배열을 만듭니다.

 

현재 정답 배열 = ( 현재 피보나치 항 * 3 ) + ( 이전 피보나치 항 * 2 ) + ( 전전 피보나치항 * 3 ) + 전전전 피보나치항

 

점화식은 그림에서 바로 확인이 가능한데, 5 기준으로 현재항( 5 )의 3개의 변, 이전항 ( 3 )의 2개의 변, 전전항 ( 2 )의 2개의 변, 마지막으로 전전전항 ( 1 ) 변 한개를 더한 값이 둘레입니다.

 

3. 정답 배열에 n을 넣고 출력합니다.

주의할 점

증가되는 방식 자체는 피보나치 수열과 같으나 타일의 둘레를 구해야합니다.

둘레도 똑같이 2까지는 초기값으로 넣어줘야 합니다.

코드 

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long long int n;
vector<int>v;
long long int p[81];
long long int ans[100];
void dp()
{
	p[0] = 0;
	p[1] = 1;
	p[2] = 1;
	ans[1] = 4;
	ans[2] = 6;
	for (int i = 3; i <= n; i++)
	{
		p[i] = p[i - 1] + p[i - 2];
		ans[i] = p[i] * 3 + p[i - 1] * 2 + p[i - 2] * 2 + p[i - 3];
	}
}
int main()
{
	cin >> n;
	dp();
	cout << ans[n];
	return 0;
}

예제 1

5

결과 1

예제 2

6

결과 2