[BOJ] 크리보드(11058)

www.acmicpc.net/problem/11058

11058번: 크리보드

난이도 - 골드5

종류 - DP

 

문제

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

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

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

입력

첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.

출력

크리보드의 버튼을 총 N번 눌러서 화면에 출력할 수 있는 A 개수의 최댓값을 출력한다.

예제 입력 1 복사

3

예제 출력 1 복사

3

예제 입력 2 복사

7

예제 출력 2 복사

9

예제 입력 3 복사

11

예제 출력 3 복사

27

힌트

N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다.

N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다.

N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V 를 눌러 27개를 출력할 수 있다.

풀이

 DP는 어렵다.. 꾸준히 해야 늘 것 같다..

1. 우선 직접 해보면 어떻게 해도 1~6은 1~6이상 나올 수 없기에 6까지 초기화 해준다.

2-1. 인덱스 7부터 보면 arr[7]은 arr[4]의 것을 5번째에 선택, 6번째에 복사 7번째에 붙여넣기를 하는 것이므로

arr[4](4)*2 = 8이 된다.

2-2. 인덱스 7에서 arr[3]에서 부터 복사작업을 했다고 가정하면 4에서 선택, 5에서 복사, 6에서 붙여넣기 7에서 붙여넣기를 한것으로 arr[3](3)*3(3, 6, 7에 각각 3씩 추가됨) = 9가 된다.

3-1. 이런식으로 직접 해보며 규칙을 찾으면 N에서는 arr[N-3]~arr[6] 까지 거꾸로 확인해가며 가장 큰 값을 찾으면 된다. 

3-2. 3번째 전 값을 복사해 쓰는 것이면 3-1인 2배 4번째 전 값을 복사해서 쓰는 것이면 4-1인 3배 j번째 전 값을 복사해서 쓰는 것이면 j-1배 만큼으로 계산하면 되기 때문에 arr[i-j]*(j-1)을 해주면 된다.

cf) 최대 값은 엄청나게 크게 나오기 때문에 int가 아닌 long long 으로 해줘야 한다.

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N;
vector<int> arr;

int main() {
	cin.tie(0); cout.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N;
	arr.resize(N+1, 0 );
	// 1~6은 화면에 그냥 쓰는 것이 가장 많이 늘리는 것이다.(6은 똑같음)
	for (int i = 1; i <= 6 && i <= N; i++) {
		arr[i] = i;
	}
	// 복사 & 붙여넣기 하려면 최소 3번째 전의 인덱스의 값을 *(3-1)배 해서 비교하면 된다.
	for (int i = 7; i <= N; i++) {
		for (int j = 3; j <= i; j++) {
			arr[i] = max(arr[i], arr[i - j] * (j - 1));
		}
	}
	cout << arr[N];
	return 0;
}