백준, boj) 11058. 크리보드 ( C / C++)

1. 문제 링크

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

11058번: 크리보드

2. 개요

크리 보드에는 버튼이 4개만 있다.

   i. 화면에 A를 출력한다

   ii. Ctrl A: 화면을 전체 선택한다.

   iii. Ctrl C: 전체 선택한 내용을 버퍼에 복사한다.

   iiii. Ctrl V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여 넣는다.

 

3. 문제 힌트

 만약에 이 문제를 완전 탐색으로 푼다면... 4가지의 선택을 100번 해야 하니까 시간 복잡도는 O(4^100)이 될 것이다.

이를 DP를 사용하여 줄여보자.

DP[index]는 index번째까지 A개수의 최댓값.이라고 정의하자.

 

고려할 점은 무엇일까

 i. 그냥 A 1개 붙이기

 ii. 선택, 복사, 붙여 넣기까지 3단계니까, dp[i-3]*2 즉, 3단계 전의 값을 복사해서 붙여 넣기.

 iii. 그다음 또 고려해야 할 것은 무엇이 있을까?

 

한번 생각을 한번 더 해보고 풀이를 보자.

 

 

4. 문제 풀이

 3단계 전의 값을 복사하는 것 까지는 좋다.

 그럼 더 나아가서 4단계 전의 값을 복사한다고 하자, 그러면, dp[i-4] * 3이 될 것이다.

 또, 5단계 전의 값을 복사한다고 가정하면, 3단계 전부터 값을 붙여 넣기 하기 시작할 것이고, 3,2,1,0 즉 4번을 복사할 수 있다. 따라서 dp[i-5]*4

이렇게 계속 나 아가다 보면,

dp[i - j] *(j-1) 이 된다. index는 1부터 시작해야 하니까, i-j > 0을 조건으로 넣어주자,

 

그리고 6까지는 모두 다 1씩 증가하는 것이 최대이기 때문에 기저 조건처럼 넣어주자.

 

이 문제의 조건 2, 3으로 끝나는 경우는 최대가 될 수 없기 때문에 생략해주자.

 

그리고 결괏값이 매우 크다.

long long 형으로 출력해주자. (64bit integer)

 

괜히 어렵게 생각했다가.. 조금 헷갈리는 문제였다.,....

 

5. 코드

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

long long int dp[101];

int main() 
{
	int n;
	scanf("%d", &n);
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	dp[4] = 4;
	dp[5] = 5;
	dp[6] = 6;

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

	}
	printf("%lld", dp[n]);
	return 0;
}

6. 결과