백준 11058 - 크리보드

문제 설명

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 N번의 조작으로 최대한 많은 A를 출력하는 길이를 구해야 한다.

 

조작하는 방법은 총 4가지이다.

1. A 출력
2. 전체 선택
3. 복사
4. 붙여 넣기

 

전체 선택 + 복사 + 붙여 넣기는 사실 한 세트라고 봐도 무방하다.

이전에 복사한 것을 붙여 넣는다 하더라도 크게 이득이 없기 때문이다.

우선 첫 A는 명백히 한 글자를 출력해야 한다.

그리고 이것을 선택 + 복사 + 붙여넣기 한다고 하면 총 4번의 조작에 2글자를 쓸 수 있다.

하지만 A를 계속 한 글자씩 출력하면 4번에는 4글자를 쓸 수 있다.

이를 일반화하여 n이라고 가정해 보자.

버퍼에 n글자가 복사되어 있다고 해보자.

그리고 이를 붙여 넣기 한 상태에서는 화면에 2n글자가 출력되어 있을 것이다.

만약 화면에 있는 글자를 다시 선택 + 복사 + 붙여 넣기 한다고하면 3번의 추가 조작으로 4n을 만들 수 있다.

하지만 3번 붙여넣기 한다면 2n + 3n으로 5n을 만들 수 있다.

따라서 선택 + 복사 + 붙여 넣기를 한 번 진행한 후 버퍼에 복사된 문자를 계속하여 붙여넣기 하는 것이 이득이다.

 

예를 들어 보자.

6번째 정답을 구한다고 해보자.

• A 6번 입력
• A 3번 입력 + 선택 + 복사 + 붙여넣기
• A 2번 입력 + 선택 + 복사 + 붙여넣기 + 붙여넣기
• A 1번 입력 + 선택 + 복사 + 붙여넣기 + 붙여넣기 + 붙여넣기

A를 4번 입력하게 되면 선택 + 붙여 넣기만 가능하므로 최대 길이를 만들어 낼 수 없다.

이를 식으로 만들면 다음과 같다.

dp[i] = max(dp[i], dp[i-j] * (j-1));

i에서 j만큼 떨어진 화면을 복사한 후 붙여 넣겠다는 뜻이다.

그리고 A를 6번 입력한 것처럼 A만 입력하는 경우도 있으니 다음과 같은 경우도 처리해 줘야 한다.

dp[i] = dp[i - 1] + 1;

---

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9
#define MAX 987654321

using namespace std;
int N;
vector<long long> dp;

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> N;
	dp.resize(N + 1, 0);

	dp[1] = 1;

	for (int i = 2; 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];

	return 0;
}

---