자바 [Algorithm] DP - 백준 11058 크리보드

1. 문제

 

 

2. 접근법

알고리즘 순서

1. N 값 받기

2. 크리보드의 4가지 역할을 사용하여 1...n번 눌렀을 때 dp배열에 최대 값을 저장

3. dp[N] 값 출력

 

경우의 수 확인

N = 1

A (1)

 

N = 2

AA (2)

 

N = 3

AAA (3)

 

N = 4

AAAA (4)

 

N = 5

AAAAA (5)

 

N = 6

AA(전체선택)(복사)(붙여넣기)(붙여넣기) : AAAAAA (6)

AAA(전체선택)(복사)(붙여넣기) : AAAAAA (6)

AAAAAA (6)

 

N = 7

A (전체선택)(복사)(붙)(붙)(붙)(붙) : AAAAA (5)

AA (전체선택)(복사)(붙)(붙)(붙) : AAAAAAAA (8)

AAA (전체선택)(복사)(붙)(붙) : AAAAAAAAA(9)

AAAA (전체선택)(복사)(붙여넣기) : AAAAAAAAA(8)

 

DP배열

1	2	3	4	5	6	7
1	2	3	4	5	6	9

 

점화식 유도

 

1번부터 6번까지는 그냥 A를 찍는게 많다.

7번부터 전체선택, 복사, 붙여넣기 과정이 들어가야 A를 더 많이 찍게된다.

 

N = 7일때 전체선택, 복사, 붙여넣기 하려면 3번을 눌러야 하므로

A를 최대한 많이 찍고 전체 선택, 복사, 붙여넣기를 해야된다.

그렇기에 dp[i-3]인 곳에 전체선택, 복사, 붙여넣기를 하면 총 7번을 누르게 된다.

그리고 붙여 넣기를 했기 때문에 dp[i-3]의 개수에서 2배가 된다.

점화식은 dp[i-3] * 2

 

하지만 미리 복사를 해놨으면 한 번 더 붙여 넣기를 했을 때 A의 개수가 증가한다.

 

dp[7] = dp[3] * 3 으로 9

따라서 dp[n] = dp[i-j] * (j-1) 

 

3. 코드

package week07;

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

public class Baek11058 {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(bufferedReader.readLine());
        long[] dp = new long[N+1];

        for (int i = 1; i <= N; i++) {
            dp[i] = i;
        }

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

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

 

 

틀린 이유는 dp 배열을 int로 선언해서 그런듯..