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

문제

https://www.acmicpc.net/problem/11058

---

문제 요약

크리보드라는 키보드에는 버튼이 4개만 존재한다.

 

A: 화면에 A를 출력한다.

Ctrl A: 화면을 전체 선택한다.

Ctrl C: 전체 선택한 내용을 버퍼에 복사한다.

Ctrl V: 버퍼가 비어있지 않은 경우, 화면에 출력된 문자열의 바로 뒤에 버퍼의 내용을 붙여 넣는다.

 

버튼을 N번 눌러 화면에 출력된 A 개수의 최대를 출력한다.

---

코드

#include <iostream>

# define ll long long

using namespace std;

ll n;

ll dp[110];

int main() {
    // 입출력 단축 코드
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;

    for (int i = 1; i < 7; i++) {
        dp[i] = i;
    }

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

    cout << dp[n];
    

    return 0;
}

---

코드 설명

Bottom Up DP를 통해 문제를 해결한다.

 

N을 1부터 차근차근 늘려가면, N이 6일 때까지는 A만 출력하는 것이 최대임을 알 수 있다.

 

N이 7이상일 경우부터는 Ctrl A, Ctrl C, Ctrl V를 한 묶음으로 생각하고 경우의 수를 따지면 된다.

 

dp[i]를 버튼을 i번 눌렀을 때, 최대 A 출력 수라고 정의하면,

 

dp[i - 5] * 4, dp[i - 4] * 3, dp[i -3] * 2 중 최대가 된다.

 

dp[i - 5] * 4

=> i - 5번 버튼을 눌러 출력한  A 최대 수에서 Ctrl A + Ctrl C + Ctrl V + Ctrl V + Ctrl V를 진행하여 A의 개수를 4배로 증가시킨 값이다.

 

dp[i - 4] * 3

=> i - 4번 버튼을 눌러 출력한  A 최대 수에서 Ctrl A + Ctrl C + Ctrl V + Ctrl V를 진행하여 A의 개수를 3배로 증가시킨 값이다.

 

dp[i - 3] * 2

=> i - 3번 버튼을 눌러 출력한  A 최대 수에서 Ctrl A + Ctrl C + Ctrl V를 진행하여 A의 개수를 2배로 증가시킨 값이다.