CodeDrive

문제:

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

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

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

입력:

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

출력:

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

풀이방법:

DP를 사용해서 해당문제를 풀도록 한다. 이 때, N이 6번까지는 ctrl+A,C,V를 사용하는 것보다 하나를 더 추가하는 것이 더 이득이기 때문에 하나씩 추가하도록 한다. 복사 붙여넣기를 하기 위해서는 최소 3개의 명령어를 사용해야 한다. 따라서 ACV, ACVV, ACVVV, ...와 같은 방법으로 붙여넣기를 진행할 수 있다. 하지만 붙여넣기는 최대 3번만 사용해도 최댓값을 구할 수 있기 때문에 ACV, ACVV, ACVVV 와 같은 3개 경우에 대해서 DP를 진행하도록 한다.

점화식은 dp[i] = max(dp[i-3-j]*(2*j), dp[i])와 같다.

문제링크:

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