[백준] 11058번 - 크리보드 / C++

문제

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

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

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

 

입력

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

 

출력

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

 

코드

#include <iostream>

using namespace std;

int N;
long long m[101];

void dp()
{
	int i, j;

	for (i = 1; i <= N; i++)
	{
		m[i] = m[i - 1] + 1;
		for (j = 3; j < i; j++)
			m[i] = max(m[i], m[i - j] * (j - 1));
	}
}

int main()
{
	cin >> N;
	dp();
	cout << m[N] << endl;
	return 0;
}

 

1부터 N까지 차례대로 각 단계에서 출력 가능한 A 개수의 최댓값을 배열 m에 저장한다.

버튼 4는 버튼 2와 3이 선행되어야 의미가 있고, 이는 화면에 출력된 A가 1개 이상이어야 의미가 있다. 따라서 4단계부터 버튼 4를 누르는 경우를 확인한다. 

j번째 값을 복사한다고 가정해보자. (j + 1) 단계에서는 버튼 2를 눌러 화면을 전체 선택하고, (j + 2) 단계에서는 버튼 3을 눌러 선택한 내용을 복사한다. 이제 (j + 3) 단계부터는 복사한 내용을 붙여 넣을 수 있다. 이때 출력되는 A의 개수는 (j + 3) 단계에서 j단계의 2배가 되고, (j + 4) 단계에서는 j단계의 3배가 된다. 즉 (j + k) 단계에서는 j단계의 (k - 1) 배의 A가 출력되는 것이다. 이 규칙을 적용하여 각 단계에서 출력 가능한 A 개수의 최댓값을 구할 수 있다.

 

링크

11058번: 크리보드

inbdni/Baekjoon