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

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

11058번: 크리보드

 

dp 정의를 먼저 하자!

dp[i] = i번째 눌렀을 때 화면 출력 최대값

 

'전체선택 - 복사 - 붙여넣기'를 한 묶음으로 생각해야 한다. 이는 세 번의 클릭이 필요한데, 일단 한번 하고 나서는 붙여넣기만 하는게 이득이다. 아래 그림을 보자.

 

위 그림은 n에서 '전체선택 - 복사 - 붙여넣기'를 한 번 한 뒤의 모습이다. 버퍼에는 원래 숫자 n이 저장될 것이고, n + 3의 위치는 2n(n+n)이 될 것이다. 여기서 '전체선택 - 복사 - 붙여넣기'를 한번 더 해준 값보다 원래 버퍼에 있는 n을 세 번 붙여넣기 한 값이 더 크다. 따라서 '전체선택 - 복사 - 붙여넣기'는 한 번만 하고, 그 뒤부터는 버퍼에 있는 값만 쭉 붙여넣기 하면 된다. 이를 그대로 구현해주면 된다.  

 

dp[9]를 예로 들어보자. dp[9]의 후보군은 아래와 같다. 

dp[6] * 2 = dp[9 - 3] * (3 - 1)
dp[5] * 3 = dp[9 - 4] * (4 - 1)
dp[4] * 4 = dp[9 - 5] * (5 - 1)
dp[3] * 5 = dp[9 - 6] * (6 - 1)
dp[2] * 6 = dp[9 - 7] * (7 - 1)
dp[1] * 7 = dp[9 - 8] * (8 - 1)

 

'A'를 한 번 입력하는 경우도 고려해줘야하므로, 이전값에 1을 먼저 더해주고 검사를 시작한다. 

 

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

int n;
long long dp[101]; // 자료형 주의!

int main() {

	cin >> n;

	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] + 1;
		for (int j = 3; j < i; j++) {
			dp[i] = max(dp[i], dp[i - j] * (j - 1));
		}
	}

	cout << dp[n] << endl;

	return 0;
}