🙇‍♀️[Gold IV] 타일 채우기 - 2133

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 1월 17일 19:33:03

문제 설명

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

🚀풀이

DP문제.

점화식을 구해야한다.

디게 생각이 안나서 8까지 경우를 생각했다.

일단 N이 홀수라면 경우의 수는 0이다.

만들수없다.

N=2라면 3이 나온다.

N=4라면 11이 나온다.

4개가 한 세트인 경우가 있다.

6개도 마찬가지로 6개가 한 세트인 경우가 있고, 8, 10 … 다 그렇다.

여차저차 해본 결과 점화식이 다음과 같다.

Cache[i] = Cache[i - 2] * 2 + 2 *(cache[i - 4] + cache[i - 6] + ... + cache[0])

이때 cache[0]은 1이다.

void solve()
{
	cin >> n;
	cache[0] = 1;
	cache[1] = 0;
	cache[2] = 3;
	cache[3] = 0;


	for (int i = 4; i <= n; ++i)
	{
		cache[i] = cache[i - 2] * cache[2];
		for (int j = i - 4; j >= 0; j = j - 2)
		{
			cache[i] += cache[j] * 2;
		}
	}

	cout << cache[n];
}

위의 점화식을 이용하면 이렇게 코드를 짤 수 있다.

아아아아아 그냥 난 노가다로 수열의 규칙찾아서 풀었다.

하다보니 나왔다.

아오 어려워.

🚀전체 코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int cache[40];
void solve()
{
	cin >> n;
	cache[0] = 1;
	cache[1] = 0;
	cache[2] = 3;
	cache[3] = 0;


	for (int i = 4; i <= n; ++i)
	{
		cache[i] = cache[i - 2] * cache[2];
		for (int j = i - 4; j >= 0; j = j - 2)
		{
			cache[i] += cache[j] * 2;
		}
	}

	cout << cache[n];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	solve();

	return 0;
}

참고