BOJ 11058 - 크리보드

문제

버튼 N번을 눌러 화면에 A를 최대한 많이 출력하라. 사용 가능한 버튼: A 출력, Ctrl-A(전체 선택), Ctrl-C(복사), Ctrl-V(붙여넣기).

입력

N이 주어진다 (1 이상 100 이하).

출력

출력할 수 있는 A의 최대 개수를 출력한다.

예제

입력	출력
`7`	`9`

풀이

DP로 i번째 버튼까지 누른 최대 A 개수를 구한다.

dp[i] = i번 눌렀을 때의 최대 A 개수
A를 한 번 누르는 경우: dp[i-1] + 1
Ctrl-A, Ctrl-C 후 Ctrl-V를 k-1번 누르는 경우: dp[i-(k+1)] * k (k=2,3,4)
모든 경우의 최댓값을 취한다

핵심 아이디어: 선택+복사에 2번, 붙여넣기에 k-1번을 사용하면 k배가 되므로, 최적은 항상 2~4배 곱하기 중 하나이다.

코드

package day599;
 
import java.io.*;
 
public class Day555BOJ11058크리보드 {
  static long[] dp;
 
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    dp = new long[n + 1];
    System.out.println(solve(n));
  }
 
  static long solve(int idx) {
    if (idx <= 0)
      return 0;
    if (idx == 1)
      return dp[idx] = idx;
    if (dp[idx] > 0)
      return dp[idx];
 
    dp[idx] = solve(idx - 1) + 1;
    for (int i = 2; i < 5; i++)
      dp[idx] = Math.max(dp[idx], solve(idx - (i + 1)) * i);
 
    return dp[idx];
  }
}

복잡도

시간: O(N)
공간: O(N)

문제