[백준] 11058번: 크리보드 문제 다이나믹 프로그래밍으로 풀기

www.acmicpc.net/problem/11058

11058번: 크리보드

문제

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

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

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

입력

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

출력

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

---

문제의 입출력 제한은 위 백준 링크에 들어가서 확인해볼 수 있다. 

이 문제는 1번 화면에 A를 출력하는 경우와 2,3,4번 control-A, control-C, control-V하는 경우를 다르게 처리해주어야 한다. 왜냐하면 control-A, control-C, control-V는 모두 연속적으로 일어나야 하기 때문이다. 하지만 꼭 세번만 일어날 필요는 없으며 control-A, control-C를 했다면 control-V는 연속적으로 여러번 누를 수 있는 문제이다. 그러면 그 때마다 처음에 전체 복사했던 값만큼이 추가될 것이다. 

 

우리는 이 문제에서 count라는 배열을 하나 만들어주고 count[i]는 i번까지 입력했을 경우 최대 A의 출력값이라고 정의를 내려본다. 

 

1. A를 하나 입력했을 경우 

그럴 경우 만약 1번 A를 단순 하나 입력했다면 점화식이 아래와 같이 작성될 수 있다. 

count[i]=count[i-1]+1

i번째 A를 입력했다면 총 A의 개수는 i-1번째까지의 값에 1을 더한 것이기 때문이다. 

 

 

하지만 만약 2, 3, 4 번을 연속적으로 진행했다고 해보자.

 

2. Control-A, control-C, control-V를 연속해서 눌렀을 경우 

그 경우에는 count[i]=count[i-3] *2 라고 정의내릴 수 있다. i-3번째 단계에서 control A, control C, control V를 연속적으로 눌러 전체 개수가 2배가 되었기 때문이다. 

 

하지만 위에서도 언급했듯이 control-V는 여러번 누를 수 있다. 만약 Control V를 두 번눌렀다고 해보자. 그 경우의 점화식은 

count[i]=count[i-4]*3 이 된다. 이처럼 우리는 control-V의 횟수에 따라서 점화식을 일반화할 수 있다는 사실을 알게 되었다. 

만약 control-V를 j 번 눌렀다고 치면 앞의 control-A, control-C 횟수까지 더하면 j+2번 누른것이다. 그 경우의 점화식은 

count[i]=count[i-(j+2)] * (j+1) 이런식으로 정의할 수 있다. 여기서 j+2를 빼기 때문에 가능한 j의 값은 1부터 i-3까지라는 것을 알 수 있다. 

---

문제에서 1번의 경우, 2번의 경우가 모두 가능하다고 했음으로 우리는 둘 중에서 더 큰 값을 택해야 한다. 먼저 1번의 경우를 배열 count에 저장하고 2번의 경우가 더 클 경우에 배열의 값을 업데이트 하는 식으로 진행하면 된다.

 

Java로 작성한 전체 코드는 아래와 같다.   

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long[] count=new long[n+1];
        for(int i=1; i<=n; i++){
            count[i]=count[i-1]+1; //한번 A를 출력하는 값
            for(int j=1; j<=i-3; j++){
               long tmp=count[i-(j+2)]*(j+1);
                count[i]=Math.max(count[i], tmp);
            }
        }
        System.out.println(count[n]);
    }
}