[BOJ / C++] 11058번 : 크리보드

문제

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

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

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

입력

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

출력

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

Solved.ac 레벨

골드 V

풀이

Solved.ac 골드 V 문제 중에 '시프트 마음대로'로 무작위로 문제를 고르는데 오늘도 DP다. 골드 V에는 DP가 은근히 많네...

언제쯤 내 머리도 다이나믹한 사고를 할 수 있을까?

 

우선 dp 배열의 dp[n] 값은 n번 버튼을 눌렀을 때 A가 출력되는 최대 개수라고 하자.

신중히 생각해야 할 것은 크리보드의 버튼 4개가 하는 기능이다.

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

1을 제외하고 2 ~ 4의 절차는 한 번에 이뤄져야 하는 절차이므로 한개로 묶어 버튼 3개를 한 번에 누르는 경우로 생각하는 것이 낫다.

그래서 dp[n]을 구할 때 2 ~ 4의 절차를 사용하는 것은 최소 3 이상부터 시작하는 것으로 한다. 이 부분은 밑에서 다시 설명하도록 하겠다.

 

손으로 여러 경우의 수를 직접 끄적여보면 n이 1 ~ 6의 값을 갖는 경우에는 dp[n] = n이다.

1 ~ 4까지는 위의 절차 2 ~ 4를 수행할 수 없기 때문이다. 

따라서 dp[1] ~ dp[6]의 경우는 1 ~ 6으로 초기화를 진행한 뒤에 n = 7인 경우부터 점화식을 사용하기로 한다.

 

그럼 예제 중 n = 7인 경우를 예를 들어서 나의 풀이 과정을 설명해보고자 한다.

점화식 반복 전 dp[7]은 0으로 초기화가 되어있다.

 

먼저 dp[7]에 들어갈 수 있는 경우의 수는 다음과 같다.

 

1. 1번 절차를 7번 수행해 A를 출력한다.

AAAAAAA //7개

2. 2 ~ 4번 절차를 수행하여 출력한다.

AAA // 버튼 3회(dp[3]) + Ctrl A + Ctrl C => 5회
AAA AAA AAA // Ctrl V 2회 
=> dp[3] * 3 => dp[7] = 9

두 경우의 수 중 최댓값을 갖는 경우를 dp[7]에 저장한다.

 

위의 절차를 반복문으로 나타내면 아래와 같다.

for(int i = 7; i <= n; i++) {
	//i = 7이라면
	for(int j = 3; i - j > 0; j++) {
    	//j의 값은 3 ~ 6.
        
        
        //반복에 따라 아래와 같은 절차를 수행한다.
        //j = 3
    	dp[7] = max(dp[7], dp[4] * 2); // 0 vs 8 => 8
        //j = 4
        dp[7] = max(dp[7], dp[3] * 3); // 8 vs 9 => 9
        //j = 5
        dp[7] = max(dp[7], dp[2] * 4); // 9 vs 8 => 9
        //j = 6
        dp[7] = max(dp[7], dp[1] * 5); // 9 vs 5 => 9
    }
}

안 쪽의 for문이 3부터 시작하는 이유는 위에서 나중에 설명하겠다고 했던 부분 때문이다.

3개의 절차를 1개로 합친 것이기 때문에 최소 버튼을 누를 수 있는 횟수가 3회 이상 확보가 되어야 하기 때문이다.

반복 조건이 i - j인 것은, 버퍼에 담길 A의 개수 때문이다.  위의 코드에서 주석으로 달아두었듯이 i = 7일때 j의 값은 3 ~ 6이 된다.

버퍼에 담을 수 있는 A의 최대값은 7 - 3의 4개부터, 최소 1개까지다. 그리고 그것들을 버튼을 누를 수 있는 잔여 횟수만큼 곱하여 기존 값과 비교하여 최댓값을 dp 배열에 담아준다.

 

따라서 점화식은 아래와 같다.

//dp[1] ~ dp[6] = 1 ~ 6

for(int i = 7; i <= n; i++) {
	for(int j = 3; i - j > 0; j++) {
    	dp[i] = max(dp[i], dp[i - j] * (j - 1));
    }
}

오늘도 어찌저찌 머리 속의 생각을 풀어내느라 힘들었다.

읽으시는 분들이 이해가 잘 되실지는 모르겠다... 글도 잘 쓰는 그날까지 힘내자

Code

#include<bits/stdc++.h>

using namespace std;

int n;
long long dp[101];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for(int i = 0; i <= 6; i++) {
        dp[i] = i;
    }

    for(int i = 7; i <= n; i++) {
        for(int j = 3; i - j > 0; j++) {
            dp[i] = max(dp[i], dp[i - j] * (j - 1));
        }
    }

    cout << dp[n] << "\n";

    return 0;
}

오늘은 DP 2 방영 시작하는 날

11058번: 크리보드