BOJ#11058 크리보드

BOJ#11058 크리보드

* 문제

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

* 풀이

- dp[i] : 버튼을 i번 눌렀을 때, 화면에 출력할 수 있는 A의 최대 개수

dp를 위와 같이 정의하고, 문제를 분석하면서 몇가지 성질을 찾아보았습니다.

0. i가 클수록 dp[i]가 무조건 크다.

1. i가 커질수록 인접한 dp값들의 차이가 커진다.

2. dp[i]의 값은 무조건 dp[i-3] * 2보다 무조건 크거나 같다. 또한 dp[i-3]의 값은 dp[i-6] * 2 보다 무조건 크거나 같다....

3. i가 일정 수준 이상이면(7이상), 이제는 A를 하나 추가하는 버튼은 필요가 없다. 복사-붙여넣기 동작만 하는 것이 A를 최대로 출력할 수 있다.

4. dp[i] 값은 i번째에 1) A를 하나 추가한 경우, 2) 버퍼에서 Ctrl + V한 경우 2가지로 나눌 수 있을 것이다.

4-1) i번째에 A를 하나 추가한 경우

dp[i] = N;

dp[i] = Max(dp[i], dp[i-1]+1)

4-2) i번째에 버퍼에서 Ctrl + V한 경우

dp[i] = Max(dp[i], dp[i-3] * 2)

dp[i] = Max(dp[i], dp[i-4] * 3)

dp[i] = Max(dp[i], dp[i-5] * 4)

dp[i] = Max(dp[i], dp[i-6] * 5)

........

이제 4-1)과 4-2)를 이용해서 구현하면 되는데

4-2)의 경우 어디까지 검사를 할 것인가..에 대해 고민을 해보면 되겠습니다.

끝까지(1까지) 검사를 할 수도 있겠지만,

대충 i-3에서 최소 i-5, 최대 10개까지만 검사를 하면 충분히 답을 얻을 수 있겠습니다.

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/master/BOJ%2311058_kriiiBoard/src/Main.java

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

/**
 * BOJ#11058 크리보드
 * https://www.acmicpc.net/problem/11058
 */

public class Main {

    static long[] dp = new long[101]; // dp[i] : 버튼을 i번 눌러서 화면에 출력할 수 있는 A의 최대 개수

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

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

        int N = Integer.parseInt(br.readLine());


        System.out.println(solve(N));
    }

    // return dp[N];
    static long solve(int N) {

        if (N <= 0) {

            return 0;
        }

        if (N == 1) {

            return dp[N] = 1;
        }

        if (dp[N] > 0) return dp[N];

        dp[N] = N;
        dp[N] = Math.max(dp[N], solve(N - 1) + 1);

        int j = 2;
        for (int i = N - 3; i > N - 6; i--) {

            dp[N] = Math.max(dp[N], solve(i) * j);
            j++;
        }

        return dp[N];
    }
}