[BOJ/백준] 11058 - 크리보드

11058번: 크리보드

---

Ctrl + A / Ctrl + C를 눌렀을 때의 최댓값 갱신

---

---

• 제목

크리보드

---

• 조건

시간 제한 : 1 초

메모리 제한 : 256 MB 

---

• 문제

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

화면에 A를 출력한다.
Ctrl-A: 화면을 전체 선택한다
Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.
크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

---

• 입력

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

---

• 출력

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

---

예제 입력1	예제 출력1
3	3

예제 입력2	예제 출력1
7	9

예제 입력3	예제 출력1
11	27

---

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

public class Main{
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        long[] dp = new long[N + 1];
        long[] ac = new long[N + 1];
        for(int i = 0; i <= N; i++){
            if(i >= 2) ac[i] = i - 2;
            dp[i] = i;
            for(int j = i - 1; j >= 2; j--) dp[i] = Math.max(dp[i], ac[j] * (i - j + 1));

            if(i >= 2) ac[i] = dp[i - 2];
        }
        System.out.println(dp[N]);
    }
}