[백준 11058번] 크리보드 (C++)

문제링크 : https://www.acmicpc.net/problem/11058

#include <bits/stdc++.h> 
using namespace std;
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);

int n;
long long dp[101];

int main()
{
	fastio;
	cin >> n;

	for (int i = 1; i <=6; i++)  //초기값 선언
	{
		dp[i] = i;
	}

	for (int i = 7; i <= n; i++)
	{
		for (int j = 4; j < i; j++)
		{
			dp[i] = max(dp[i], dp[i - j] * (j - 1));  //점화식
		}
	}
	cout << dp[n];
}

 

값의 범위가 크다보니 dp 배열을 long long으로 선언했다.

다음으로 처음 dp[1~6]까지는 초기값으로 1~6을 선언했다.

그다음 경우의 수가 2가지인데, 그대로 프린트만 하는 경우와 출력한 것을 복사하고 다시 붙여넣어 출력하는 경우다.

(A / Ctrl-A, Ctrl-C, Ctrl-V)

이에 대한 점화식을 세우고, 둘 중 큰 값을 출력하면 된다.