백준 11058. 크리보드

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

11058번: 크리보드

 

dp 문제.

 

버튼의 역할은 다음과 같다. 

 

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

 

우리는 버튼을 N번 눌렀을때 화면에 출력되는 A의 최대갯수를 찾는 것이기 때문에, 잘 생각해보면 2,3,4번 버튼은 하나의 버튼으로 생각해야 된다. 

그런데 또 생각해야 할 점은 2,3번 버튼을 누르고 난 후에는 (전체선택 후 버퍼에 복사) 4번 버튼은 계속 누를수 있다는 점이다.

 

d[i] : 버튼을 i번 눌렀을때 화면에 나타나는 A의 최대 갯수 

 

예를들어 버튼을 4번 눌렀을때를 생각해 보자.

우선 1번만 4번 눌렀을때 AAAA로 d[4] = 4 일것이다. 

이 상태에서 2,3,4번 버튼을 누르면 버튼을 누른 횟수는 (4+3) = 7번 눌렀고, 화면에 나타나는 A의 수는 (4*2) = 8개 이다. 

그렇다면 d[7] = 8이다. 

 

즉 버튼을 7번 눌렀을때 화면에 나타나는 A의 최대갯수는 8개다. 

그런데 이 과정에서 2,3번 버튼을 눌렀으니 버퍼에는 A가 4개 있는 상태다. 

따라서 지금 부터는 4번 버튼만 눌러서 뒤에 A를 4개씩 계속 붙여줄수 있다. 

d[7] = 8 

d[8] = 12

d[9] = 16 

...

 

점화식은 

d[i] = max(d[i], d[i-1]+1, d[j] * (i - j -1))