Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 4키 키보드 문제: 최대 개수의 'A' 출력하기

문제 이해하기

키보드에서 딱 네 개의 키만 사용해 화면에 최대한 많은 문자 'A'를 출력하는 것이 이 글의 목표입니다. 사용할 수 있는 키는 'A', 'C', 'V', 그리고 'Ctrl'입니다.

가장 많은 'A'를 만들기 위해서는 다음 키 조합을 활용해야 합니다.

  • Ctrl + A : 전체 선택
  • Ctrl + C : 복사
  • Ctrl + V : 붙여넣기

예를 들어 키 입력 횟수가 7번이라면 정답은 9가 됩니다. 먼저 'A'를 세 번 누른 뒤, 이어서 Ctrl+A(전체 선택), Ctrl+C(복사), Ctrl+V(붙여넣기), Ctrl+V(붙여넣기) 순서로 입력하면 화면에는 총 9개의 'A'가 표시됩니다.

해결 접근 방법

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

  • 키 입력이 6회 이하라면 매번 'A'를 직접 누르는 것이 최선이므로, 결과는 곧 키 입력 횟수와 같습니다.
  • 7회부터는 특정 시점(분기점)까지 'A'를 눌러 만든 결과를 복사한 후, 남은 입력 횟수만큼 붙여넣기를 반복하는 전략을 고려합니다.

구체적인 알고리즘 단계는 다음과 같습니다.

  1. keyStrokes ≤ 6이면 keyStrokes를 그대로 반환합니다.
  2. n = 1부터 6까지 result[n-1] = n으로 초기화합니다.
  3. n = 7부터 keyStrokes까지 다음을 반복합니다.
    • result[n-1]을 0으로 초기화합니다.
    • 분기점(breakpoint)을 n-3부터 1까지 역순으로 탐색하며 curr = (n − breakpoint − 1) × result[breakpoint − 1]을 계산하고, 기존 값보다 크면 갱신합니다.
  4. 최종적으로 result[keyStrokes − 1]을 반환합니다.

여기서 분기점이란 'Ctrl+A, Ctrl+C, Ctrl+V' 연산을 시작하기 직전, 즉 마지막으로 'A'를 누른 시점을 의미합니다. 분기점 이후에는 전체 선택과 복사에 2회의 입력이 추가로 필요하므로, 분기점은 최소 n−3까지만 탐색하면 됩니다.

예제 코드

다음 C++ 구현을 통해 더 쉽게 이해할 수 있습니다.

#include<iostream>
using namespace std;

// 4가지 키로 만들 수 있는 'A'의 최대 개수 구하기
int keyNumbers(int keystrokes){
    // 키 입력이 6회 이하라면 모두 'A'를 누르는 것이 최적
    if (keystrokes <= 6)
        return keystrokes;

    int result[keystrokes]; // 중간 결과를 저장할 배열

    // 6회까지는 키 입력 횟수 자체가 최대 'A' 개수
    for (int n = 1; n <= 6; n++)
        result[n-1] = n;

    // 7회부터는 동적 계획법 적용
    for (int n = 7; n <= keystrokes; n++){
        result[n-1] = 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;
}

입력

7

출력

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

정리

이 문제의 핵심은 '직접 입력'과 '복사 후 붙여넣기' 중 어느 시점에 전략을 전환하는 것이 유리한지를 수학적으로 판단하는 것입니다. 동적 계획법을 활용하면 모든 가능한 분기점을 체계적으로 비교하여, 주어진 키 입력 횟수로 얻을 수 있는 최대 'A' 개수를 정확히 구할 수 있습니다.