[BOJ G5][#DP]11058번 크리보드

크리보드 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

7585

3408

2728

44.135%

문제

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

1. 화면에 A를 출력한다.
2. Ctrl-A: 화면을 전체 선택한다
3. Ctrl-C: 전체 선택한 내용을 버퍼에 복사한다
4. Ctrl-V: 버퍼가 비어있지 않은 경우에는 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여넣는다.

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

입력

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

출력

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

예제 입력 1 복사

3

예제 출력 1 복사

3

예제 입력 2 복사

7

예제 출력 2 복사

9

예제 입력 3 복사

11

예제 출력 3 복사

27

 

📝풀이

이번에 DP에 대해 집중적으로 풀어보는데 나 DP 정말 못하는거 같다...

 

 

일단 문제를 보고 BFS를 사용해보았다. 

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

public class Main {
    static int N;
    static int result = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        bfs();
        System.out.println(result);
    }

    public static void bfs() {
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0, 0}); // {A, clipboard, count}

        while (!q.isEmpty()) {
            int[] num = q.poll();
            int A = num[0];
            int clipboard = num[1];
            int count = num[2];

            if (count > N) continue; 

            result = Math.max(result, A);

            if (count + 1 <= N) q.add(new int[]{A + 1, clipboard, count + 1});

            if (count + 2 <= N) q.add(new int[]{A, A, count + 2});

            if (clipboard != 0 && count + 1 <= N) q.add(new int[]{A + clipboard, clipboard, count + 1});
        }
    }
}

간단하고 편안하게 구현하고 돌렸는데 결과는..

자 진짜 DP 문제인걸 알았으니 점화식을 짜보자 

 

📌 아이디어

기본규칙
A : A를 입력한다.
B : 해당 텍스트 전체 선택
C : 해당 텍스트를 클립보드에 복사
D : 붙여넣기 

초기 식 
dp[1] = A 1개
dp[6] = AAABCD 6개, AAAAAA
dp[7] = AAABCDD 9개
dp[8] = AAABCDDD 12개
dp[9] = AAAABCDDD 20개 

1. A만 누르는 수
2. BCD를 하는 수
3. BCDD를 하는 수
4. BCDDD를 하는 수 

변환하기
1. DP[i]
2. DP[i-3] * 2
3. DP[i-4] * 3
4. DP[i-5] * 4

점화식
DP[i] = Math.max(DP[i], DP[i-3] * 2, DP[i-4] * 3, DP[i-5] * 4)

import java.io.*;

public class Main {
    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(getMaxAs(N));
    }

    public static long getMaxAs(int N) {
        if (N <= 6) return N; // 6번 이하의 입력은 모든 경우에 직접 출력이 최댓값입니다.

        long[] dp = new long[N + 1];

        // 초기값 설정
        for (int i = 1; i <= N; i++) {
            dp[i] = i;
        }


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

        return dp[N];
    }
}