[백준] 11058: 크리보드 - JAVA

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

 

풀이

크리보드는 전체 선택, 복사, 붙여넣기, 출력 버튼이 있다.

 

버튼을 N번 눌러서 화면에 출력된 A개수를 최대로 하는 방법을 찾아야 한다.

 

DP를 이용해 해결했다.

 

DP배열을 초기화 후 DP배열을 채우면서 최적의 결과를 찾는다.

 

for (int i = 1; i < n + 1; i++) {
    dp[i] = dp[i - 1] + 1; // 기본적으로 'A'를 하나 추가

    if (i > 6) { // 6번 이후부터는 복사&붙여넣기를 고려
        for (int j = 3; j <= 5; j++) { // 3번, 4번, 5번 키를 누른 경우
            dp[i] = Math.max(dp[i - j] * (j - 1), dp[i]);
        }
    }
}

 

 

---

 

메모리: 14204KB
시간: 124ms
언어: Java 11

import java.io.*;
import java.util.*;

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 < n + 1; i++) {
            dp[i] = dp[i - 1] + 1;
            if (i > 6) {
                for (int j = 3; j <= 5; j++) {
                    dp[i] = Math.max(dp[i - j] * (j - 1), dp[i]);
                }
            }
        }

        System.out.println(dp[n]);
    }

}