백준 BOJ 11058 - 크리보드

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

11058번: 크리보드

DP 문제.

DP[i] 를 버튼을 i번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값으로 만든다.

DP[i] 의 기초 값은 DP[i-1] + 1 이다. ( 1번 버튼 화면에 A를 출력한다를 사용 )

 

2, 3, 4번 연산은 사실상 한 세트라고 생각하면 되는데,

어떠한 값을 붙여넣기 위해서는 3번의 연산이 필요하므로

dp[i-3]*2 값으로 dp[i]를 갱신 할 수 있다.

 

이때 붙여넣기를 연속으로 두번 하는 경우가 존재하는데,

붙여넣기를 연속으로 두번 하기 위해서는

 

ctrl-A / ctrl-C / ctrl-V / ctrl-V

 

이렇게 네번의 연산을 필요로 하므로,

dp[i-4]*3 값으로 dp[i]를 갱신할 수 있다.

이러한 형태가 쭈욱 반복되게 되므로,

 

j를 [1,i-3] 사이의 임의의 값이라고 할때,

dp[i]를 dp[j] * (i-j-1) 값과 비교하며

최댓값으로 갱신해주면 정답을 얻을 수 있다.

 

수의 범위가 커질 수 있으므로

long long 형으로 선언해야 한다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll dp[123] = {0}; // dp[i] -> i번 눌러서 만들수있는 최댓값. 


int main(){
	dp[1] = 1;
	for(int i=2; i<=100; i++){
		dp[i] = dp[i-1]+1;
		for(int j=1; j<=i-3; j++){
			dp[i] = max(dp[i], dp[j]*(i-j-1));
		}
	}
	
	int N;
	cin >> N;
	cout << dp[N];
	return 0;
}