[백준 11058] 크리보드 (JAVA)

문제

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

풀이

DP를 이용한 문제입니다. 전체 선택 -> 복사 -> 붙여넣기는 3번의 동작이 필요합니다. 붙여넣기 이후에는 계속 붙여넣기를 할 수 있으므로 전부 확인해줘야 합니다. (테스트해본 결과 3번 붙여넣기 안에서 최댓값이 나오는 거 같습니다)

7번 버튼을 눌렀을 때 붙여넣기는 3번의 동작이 필요하므로 4번의 A갯수의 2배이므로 8입니다. 그러나 3번에서 붙여넣기를 두 번 하면 9가 되고 2번에서 붙여넣기를 세 번 하면 8이 되므로 가장 큰 수는 9입니다.

코드

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

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        long[] dp = new long[N+1];
        for (int i = 1; i <= Math.min(N, 6); i++) {
            dp[i] = i;
        }

        for (int i = 7; i <= N; i++) {
            for (int j = 2; j <= 5; j++) {
                dp[i] = Math.max(dp[i-(j+1)] * j, dp[i]);
            }
        }

        System.out.println(dp[N]);
        br.close();
    }
}