4개의 키만 사용해 최대 개수의 'A'를 출력하는 방법 (동적 계획법)

키보드로 문자 'A'를 입력하는 상황을 가정해 보겠습니다. 목표는 'A', 'C', 'V', 'Ctrl' 단 네 개의 키만 사용하여 텍스트 화면에 최대한 많은 'A'를 출력하는 것입니다.

가장 많은 'A'를 만들기 위해서는 Ctrl + A(전체 선택), Ctrl + C(복사), Ctrl + V(붙여넣기) 조합을 전략적으로 활용해야 합니다.

문제 이해하기

6번 이하의 키 입력에서는 매번 'A' 키를 직접 누르는 것이 최선입니다. 하지만 7번부터는 중간에 전체 선택 → 복사 → 붙여넣기를 수행하는 것이 더 유리해집니다. 예를 들어, 7번의 키 입력이 주어지면 다음 순서로 9개의 'A'를 만들 수 있습니다.

• A, A, A — 화면에 'AAA' 출력
• Ctrl + A — 'AAA' 전체 선택
• Ctrl + C — 'AAA' 복사
• Ctrl + V, Ctrl + V — 두 번 붙여넣어 총 9개의 'A' 확보

입력과 출력

입력:
키 입력 횟수 N (예: 7)

출력:
N번의 키 입력으로 만들 수 있는 A의 최대 개수 (예: 9)

알고리즘 접근 방식

이 문제는 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 키 입력이 6회 이하라면 모든 입력을 'A' 타이핑에 사용하는 것이 최적이므로, 키 입력 횟수를 그대로 반환합니다.
2. 7회 이상부터는 특정 지점(분기점, breakpoint)까지 직접 타이핑하고, 남은 키 입력으로 전체 선택·복사·붙여넣기를 수행하는 경우를 모두 고려합니다.
3. 분기점 b까지 result[b−1]개의 'A'가 있다면, 남은 (n − b − 1)번의 입력(전체 선택 1회, 복사 1회, 나머지는 붙여넣기)으로 (n − b − 1) × result[b−1]개를 만들 수 있습니다.
4. 모든 분기점을 시도하며 최댓값을 저장합니다.

의사 코드

입력: 키 입력 횟수
출력: 해당 키 입력으로 얻을 수 있는 최대 문자 수

Begin
    if keyStrokes <= 6, then
        return keyStrokes

    for n := 1 to 6, do
        result[n-1] := n
    done

    for n := 7 to keyStrokes, do
        result[n-1] := 0
        for breakpoint := n-3 down to 1, do
            curr := (n – breakpoint - 1) * result[breakpoint - 1]
            if curr > result[n-1], then
                result[n-1] := curr
        done
    done
    return result[keyStrokes - 1]
End

C++ 구현 예제

#include<iostream>
using namespace std;

int keyNumbers(int keystrokes) {    // 4종류의 키로 만들 수 있는 'A'의 개수 계산
    if (keystrokes <= 6)    // 키 입력이 6회 이하인 경우
        return keystrokes;

    int result[keystrokes];    // 중간 결과를 저장할 배열
    for (int n=1; n<=6; n++)    // 6회까지는 입력 횟수 자체가 최댓값
        result[n-1] = n;

    for (int n=7; n<=keystrokes; n++) {    // 7회 이상 처리
        result[n-1] = 0;    // 초기값 0으로 설정
        for (int breakPoint=n-3; breakPoint>=1; breakPoint--) {    // 선택·복사·붙여넣기 분기점 탐색
            int curr = (n-breakPoint-1)*result[breakPoint-1];
            if (curr > result[n-1])
                result[n-1] = curr;
        }
    }
    return result[keystrokes-1];
}

int main() {
    int keystrokes;
    cout << "Enter Number of keystrokes: "; cin >> keystrokes;
    cout << "Maximum Number of A's with "<<keystrokes << " keystrokes is: "<< keyNumbers(keystrokes)<<endl;
}

실행 결과

Enter Number of keystrokes: 7
Maximum Number of A's with 7 keystrokes is: 9

마무리

이 알고리즘은 바깥쪽 반복문과 안쪽 분기점 탐색 반복문으로 인해 O(N²)의 시간 복잡도를 가집니다. 키 입력 횟수가 커질수록 복사·붙여넣기를 활용하는 것이 직접 타이핑보다 훨씬 효율적이라는 점이 이 문제의 핵심입니다.