글 읽기 - 동적 프로그래밍 고수님들 타일채우기 한수 부탁드립니다

tddhot2 7년 전 0

제가 생각한 방법은 이렇습니다.

아래 첨부한 그림처럼 왼쪽의 경우는 이미 최적의 개수가 구해졌으니 나머지 추가된 2칸에 대해서 곱을 해서 경우의 수를 세고,

우측의 칸수가 늘어날 때 생기는 특수의 경우는 따로 빼줘서 계산을 해줍니다.

그런식으로 증가시키는 것인데 잘못된것일까요?

#include <iostream>
#include <vector>
using namespace std;

void PrintArray(int* arr, int n)
{
	for (int i = 0; i <= n; i++)
		cout << arr[i] << endl;;
	cout << "\n" << endl;
}

int main()
{
	int dp[31];
	fill_n(dp, 31, 0);

	dp[0] = 1;
	dp[2] = 3;

	//특수 경우를 구하기 위한 변수
	int memoiValue = 1;

	for (int i = 4; i <= 30; i+=2)
	{
		if(i!=4)
			memoiValue += dp[i - 4] * 2;

		dp[i] = dp[2] * dp[i - 2]+memoiValue; // 왼쪽의 일반적인 경우

	}
	//PrintArray(dp, 30);

	int n;
	cin >> n;
	cout << dp[n] << endl;
	return 0;
}

jjwdi0 7년 전 1

작성자분께서 말씀하신 특수 경우가 위아래 뒤집으면 두 개 아닐까요?

tddhot2 7년 전 0

생각해보니 그런경우가!!!

한번 시도해보고 다시 말씀드릴게요 감사랍니다!

tddhot2 7년 전 0

해당 경우수를 추가해도 안되네요...

휴 ㅜㅜ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

동적 프로그래밍 고수님들 타일채우기 한수 부탁드립니다

tddhot2 7년 전 0

jjwdi0 7년 전 1

tddhot2 7년 전 0

tddhot2 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말