[Java] 백준 크리보드

문제

11058번: 크리보드 (acmicpc.net)

11058번: 크리보드

알아야 할 개념

• 점화식
• dp

풀이

버튼 4가지의 역할은 다음과 같다.

1. A를 출력
2. 전체 선택
3. 선택 영역 복사
4. 붙여넣기

알수 있는 규칙은 단순히 A를 추가하면 현재 길이 + 1 가 되고 , 붙여넣기를 하면 현재 단계 i 에서 3번째 전 단계의 것을 가져와서 붙여넣기를 한다.

붙여넣기를 할 때 특징은 다음과 같다.

• 3번쨰 전 것을 가져오면, 1번 붙여넣기를 할수 있다. = dp[ i-3 ] * 2 (3번째 전것의 값 x 2 ) 
• 4번째 전의 것을 가져오면 2번 붙여넣기 가능 = dp[ i-4 ] * 3 ( 4번째 전것의 값 x 3 )
• k번째 전의 것을 가져오면, k-2번 붙여넣기 가능  = dp[ i-k ] * (k-1) (k번째 전 것의 값 x (k-1) ) 

이 논리를 이용한 풀이는 다음과 같다. 

1. 현재 단계 dp[i] 의 값을 dp[i-1]+1 로 초기화한다. (단순히 A 추가)
2. 반복문으로 3 이상 i 이하의 값을 k 에 대입하여, dp[i] 의 값을 업데이트 한다. 
3. dp [N] 을 리턴한다.
4. 정답의 크기가 매우 큼으로 long형을 사용

코드

자바

import java.io.*;
import java.util.*;
public class Main {

    int N;
    public static void main(String[] args) throws IOException {
        Main m = new Main();
        System.out.println(m.solution());
    }
    public long solution() throws IOException {
        FastReader fr = new FastReader();
        int N = fr.nextInt();
        long[] dp = new long[101];
        for(int i = 1 ;i < N+1 ;i++){
            dp[i] = dp[i-1]+1;
            for(int j = 3; j < i ; j++){
                dp[i] = Math.max(dp[i], (j-1)*dp[i-j]);
            }
        }
        return dp[N];
    }

    public static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}