[Java] BaekJoon 11058. 크리보드 (골드5) (DP)

문제출처: https://www.acmicpc.net/problem/11058

11058번: 크리보드

 

문제이해

 

목표

크리보드는 kriii가 만든 신기한 키보드이다. 크리보드에는 버튼이 4개만 있으며, 하는 역할은 다음과 같다.
화면에 A를 출력한다.
Ctrl-A: 화면을 전체 선택한다
Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

크리보드의 버튼을 총 N번 눌러서 화면에 출력된 A개수를 최대로하는 프로그램을 작성하시오.

 

풀이

 

버튼 1개눌렀을 때부터 N까지 선형 탐색 (i)

 -> i 이전 인덱스의 값을 기준으로

     전체선택, 복사(2소요) -> 붙여넣기(1씩 소요) 했을 때의 값으로 갱신한다. 

     선택하고, 복사하는데 비용이 2들고, 추가적으로 한번더 붙여넣기를 했다 가정하니까 비용이3. i-1 -> i +2  

     즉, j는 i+2부터 갱신

     

-> 그리고 < longArr[i]의 값 = Max(이전 인덱스의 값 + 1, longArr[i]의 값> 이 된다.

 

소스코드

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

public class 크리보드 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long[] longArr = new long[N];
        longArr[0] = 1;
        for (int i = 1; i < N; i++) {

            long num = longArr[i - 1];
            long temp = num;
            for (int j = i + 2; j < N; j++) {
                temp += num;
                longArr[j] = Math.max(temp, longArr[j]);
            }

            longArr[i] = Math.max(longArr[i-1] + 1, longArr[i]);
        }
        System.out.println(longArr[N-1]);
    }
}