[백준] 11058 크리보드

⚡백준 11058 크리보드

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

• 백준 14226 이모티콘과 유사한 문제

• 주어진 시간 3초 미만일 때 가능한 경우:
  1초 전 상태에 A를 하나 추가하기 = 1초 전 상태 + 1

• 주어진 3초일 때 가능한 경우:
  3초 전 상태 전제 선택, 복사, 붙여넣기 = 3초 전 상태 X 2

• 주어진 시간 4초일 때 가능한 경우:
  3초 전 상태 전체 선택, 복사, 붙여넣기 = 3초 전 상태 X 2
  4초 전 상태 전체 선택, 복사, 붙여넣기, 붙여넣기 = 4초 전 상태 X 3

• 주어진 시간 5초일 때 가능한 경우:
  3초 전 상태 전체 선택, 복사, 붙여넣기 = 3초 전 상태 X 2
  4초 전 상태 전체 선택, 복사, 붙여넣기, 붙여넣기 = 4초 전 상태 X 3
  5초 전 상태 전체 선택, 복사, 붙여넣기, 붙여넣기, 붙여넣기 = 5초 전 상태 X 4

• 주어진 시간 time일 때 가능한 경우:
  (2+1)초 전 상태 전체 선택, 복사, 붙여넣기 = (2+1)초 전 상태 X (1+1)
  (2+2)초 전 상태 전체 선택, 복사, 붙여넣기 = (2+2)초 전 상태 X (1+2)
  ...
  (2+i)초 전 상태 전체 선택, 복사, 붙여넣기 = (2+i)초 전 상태 X (1+i)

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAX = 101;

int N;
long long cache[MAX];

long long getScreen(int time){

	long long &res = cache[time];
	if (res != -1) return res;

	//1초전 상태에 A 하나 추가
	res = 1 + getScreen(time - 1);

	if (time >= 3) {
		//(time- 2 - i)초 상태에 CtrlA + CtrlC + Σ(CtrlV)
		for (int i = 1; time - 2 - i >= 0 ; ++i) {
			res = max(res, getScreen(time - 2 - i) * (i + 1));
		}
	}
	return res;
}



int main(){

	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);

	memset(cache, -1, sizeof(cache));

	cin >> N;

	cache[0] = 0;
	cout << getScreen(N);
	return 0;
}

📌참고자료

• 백준 11058 크리보드 풀이
  https://kibbomi.tistory.com/96
  https://jaimemin.tistory.com/1098