BOJ 11058 - 크리보드

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

출력 결과에 영향을 미치는 연산이 A를 그냥 누르는 거랑(+1), Ctrl-V (+복사했던 크기) 인데 클립보드에 복사해놓은 크기때문에 재귀로 짜는데 애를 먹었다.

복사한 크기만큼 늘어나기 때문에, Ctrl-V 를 하기 위해서는 이전에 Ctrl-A, Ctrl-C 가 꼭 필요하다.

문제에 적힌 연산을 순서대로 A, S, C, V 라고 한다면 $N=6$인 경우는 아래와 같이 가능하다.

AAAAAA

AAASCV

AASCVV

ASCVVV

이 정도가 의미있는 타이핑인거같다. 타이핑을 $n$번한 것을 $f(n)$이라 하자. 그럼 위 4줄은 각각 $f(5)+1$, $f(3)∗2$, $f(2)∗3$, $f(1)∗4$ 이다.

$$f(0) = 0, f(n) = \begin{cases} f(n-1) + 1, \\ f(k) * (n-k-1), & \text{if $k$ < n - 4 } \end{cases}$$

코드

	#include <bits/stdc++.h>
	using namespace std;
	typedef long long lld;
	int main(){
	int n;
	scanf("%d", &n);
	lld dp[101]={};
	for(int i=1; i<=n; ++i){
	dp[i] = dp[i-1]+1;
	for(int k=n-3; j>=0; --j){
	dp[n] = max(dp[n], dp[k] * (n-k-1));
	}
	}
	printf("%lld", dp[n]);
	return 0;
	}

view raw boj-11508.cpp hosted with ❤ by GitHub