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

풀이

문제를 쉽게 풀어보면 그냥 N의 비용으로 결과값을 최대로 만드는 문제이다. 결과값을 증가시키기 위해 네 가지 행동을 할 수 있는데 Brute-force로 N = 20 정도까지만 탐색해봐도 N이 7 이상일때는 A를 하나씩 출력하는 방법은 절대 답이 될 수 없다. 이 경우를 배제하면 남은 할 수 있는 행동은 두가지이다.

  • N - 3의 상태에서 전체 선택 - 복사 - 붙여넣기
  • N - 3이전의 상태에서 복사 후 계속 붙여넣기

그런데 위 겹치는 부분 문제이기 때문에 아래의 방법으로 요약이 가능하다.

  • N - 3를 포함한 이전의 상태에서 복사 후 계속 붙여넣기

아래 코드는 위 풀이에 대한 구현이다.

코드

#include <cstdio>
typedef unsigned long long ULL;
ULL max(ULL x, ULL y) { return x > y ? x : y; }
int main() {
	int n;
	ULL dp[101];
	scanf("%d", &n);
	for (int i = 0; i <= 100; i++) {
		if (i < 7) {
			dp[i] = i;
		}
		else {
			dp[i] = i;
			for (int j = i - 3, k = 2; j > 0; j--, k++)
				dp[i] = max(dp[i], dp[j] * k);
		}
	}
	printf("%llu", dp[n]);
}