11058번 - dp, 규칙찾기

문제:

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

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

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

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

 

 

풀이:

딱봐도 규칙을 찾아야 할듯한 문제이다.

bfs나 dfs로 하기에는 경우의수가 너무나도 많아진다.

A는 입력, a는 ctrl-a, c는 ctrl-c, v는 ctrl-v를 뜻한다.

일단 한번 작성해보도록 하자.

1	A
2	AA
3	AAA
4	AAAA
5	AAAAA

위와 같이 1~5까지는 복붙이 필요 없다. 어짜피 손해이기 때문이다.

6	AAAAAA AAacvv = 6

6부터 복붙이 그냥 쓰는 것과 동일해지기 시작한다. 그렇다면 7부터 규칙성이 보일때까지 작성해보도록 하겠다.

7	AAacvvv = 8 AAAacvv = 9 AAAAacv = 8
8	AAAacvvv = 12 AAAAacvv = 12 AAAAAacv = 10
9	AAAAacvvv = 16 AAAAAacvv = 15 AAAAAAacv = 12

음... 뭔가 있는듯 하지만 아직 확신할 순 없다.

확실한건 AAAAAA 보다 max6이 더 표기하기 좋고, 7부터는 max7로 하지 않는 이상 정확한 답을 찾기 어려울 것이다.

dp 문제가 확실해졌다.

10	max4 x 5 = 20 max5 x 4 = 20 max6 x 3 = 18 max7 x 2 = 18
11	max5 x 5 = 25 max6 x 4 = 24 max7 x 3 = 27 max8 x 2 = 24
12	max7 x 4 = 36 max8 x 3 = 36 max9 x 2 = 32
13	max8 x 4 = 48 max9 x 3 = 48 max10 x 2 = 40
14	max9 x 4 = 64 max10 x 3 = 60
15	max10 x 4 = 80 max11 x 3 = 81
16	max11 x 4 = 108 max12 x 3 = 108
17	max12 x 4 = 144 max13 x 3 = 142

이제는 확실하게 규칙을 찾았을 것이다.

max[now] = max[now-5] * 4 vs max[now-4] * 3

결국 두 수만 비교하면 해당 위치의 최댓값을 알 수 있다.

 1~5까지 저장한 후 max[now] = max[now-5] * 4 vs max[now-4] * 3 공식을 코드로 기입하면 될 것이다.

 

전체코드:

import java.util.Scanner;

public class 크리보드_11058번 {
    static int N;
    static long[] criBoard;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        criBoard = new long[N+6];
        for (int i = 1; i <= 5; i++) {
            criBoard[i] = i;
        }

        findMax();
        System.out.println(criBoard[N]);
    }

    static void findMax() {
        for (int i = 6; i <= N; i++) {
            criBoard[i] = Math.max(criBoard[i-5]*4, criBoard[i-4]*3);
        }
    }
}

 

cirBoard의 크기가 N+6인 이유는 1~5까지는 다른 조건 없이 저장해놓고 싶었기 때문이다.

 

시행착오:

코드는 정말 짧았지만, 규칙찾는 과정이 너무 귀찮았다.

그래도 열심히 쓴 덕분에 점화식이 max[now] = max[now-5] * 4 vs max[now-4] * 3 라는 것을 알 수 있었다.

조금 덜 써봤더라면, 비교과정이 한번 더 들어갔을 것이다.

시험을 보는 입장이라면, 비교과정이 한번 더 들어가도 규칙을 적당히 찾고 끝내는 것이 좋을 것이고,

어떤 프로그램에 적용시키는 것이라면, 규칙을 꼼꼼하게 찾고 비교과정을 한번 줄이는 게 좋을 것같다.