[BaekJoon] 11058 크리보드 (Java)

1.  문제 링크

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

2.  문제

요약

• 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같습니다.
  1. 화면에 A를 출력합니다.
  2. Ctrl-A : 화면을 전체 선택합니다.
  3. Ctrl-C : 전체 선택한 내용을 버퍼에 복사합니다.
  4. Ctrl-V : 버퍼가 비어있지 않은 경우, 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣습니다.
• 크리보드의 버튼을 N번 눌러서 화면에 출력되는 A의 개수의 최댓값을 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 100보다 작거나 같은 N이 주어집니다.
• 출력: 첫 번째 줄에 크리보드의 버튼을 N번 눌러 화면에 출력할 수 있는 A 개수의 최댓값을 출력합니다.

3.  소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	public long getMaxNum(int num) {
		long[] dp = new long[num + 1];
		for(int i = 1; i < dp.length; i++) {
			dp[i] = dp[i - 1] + 1;
			if(i > 6) {				
				for(int j = 2; j < 5; j++) {
					dp[i] = Math.max(dp[i], dp[i - (j + 1)] * j);
				}
			}
		}
		return dp[num];
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int num = Integer.parseInt(br.readLine());
		br.close();
		Main m = new Main();
		bw.write(m.getMaxNum(num) + "\n");
		bw.flush();
		bw.close();
	}
}

4.  접근

• 해당 문제는 DP를 이용하여 구할 수 있는 문제입니다.
• N이 1보다 크거나 같고 6보다 작은 경우는 최대로 출력될 수 있는 A의 개수는 N과 같습니다.
• Ctrl-A, Ctrl-C, Ctrl-V를 진행할 때, 한 번의 Ctrl-A, Ctrl-C를 통하여 Ctrl-V를 4번 이상 한다면 이는 출력될 수 있는 A의 개수를 최대로 만들어주지 못하므로 한 번의 Ctrl-A, Ctrl-C로 최대 3번의 Ctrl-V를 진행할 수 있습니다.
• 이를 이용하여 바로 이전 값에서 A의 개수를 1 늘린 수와 Ctrl-V를 2번, 3번, 4번 진행한 경우에 대해 각각의 A의 수를 구하여 그 중 가장 큰 값이 현재 값에서의 출력될 수 있는 A의 최대 개수가 됩니다.
  • $dp[i]$ = $i$ ($1 \leq i \leq 6$)
  • $dp[i]$ = $max(dp[i - 1] + 1, dp[i - 3] \times 2, dp[i - 4] \times 3, dp[i - 5] \times 4)$ ($i \leq 6$)
• 위 점화식을 이용하여 출력될 수 있는 A 개수의 최댓값을 구합니다.

1. 1부터 N까지 각 횟수에서 출력될 수 있는 A의 최대 개수를 나타내는 1차원 배열 dp을 생성합니다.
2. 1부터 N까지 반복문을 돌며 출력될 수 있는 A의 최대 개수를 구합니다.
   1. 현재 횟수에서의 값을 (이전 횟수에서의 값 + 1)로 초기화합니다.
   2. 만약 현재 횟수가 6보다 크다면 위에서 구한 점화식을 바탕으로 2부터 4까지 반복문을 돌며 붙여넣기를 2번, 3번, 4번 했을 때의 A의 개수를 구하여 현재 횟수에서의 값과 붙여넣기를 했을 때의 값들을 비교하여 가장 큰 값을 현재 횟수에서의 값으로 설정합니다.
3. 2번의 반복문이 끝났을 때의 dp[N]의 값이 화면에 출력할 수 있는 A 개수의 최댓값이므로 이를 출력합니다.