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

C++로 정수 n을 만드는 데 필요한 최소 알파벳 개수 구하기

문제 설명

정수 n이 주어졌을 때, 알파벳 소문자를 각각 a = 1, b = 2, c = 3, ..., z = 26과 같은 값으로 대응시킨다고 가정해 봅시다. 이때 이 알파벳들의 값을 합하여 정확히 n이 되도록 만들기 위해 필요한 최소한의 글자 수를 구하는 것이 과제입니다.

예시

n = 23인 경우 → 출력: 1 (w 한 글자로 표현 가능)
n = 72인 경우 → 출력: 3 (26 + 26 + 20)

예를 들어 n이 23이라면 'w'라는 한 글자만으로 값을 만들 수 있으므로 필요한 글자 수는 1입니다. 반면 n이 72라면 z(26) 두 개와 t(20) 하나, 즉 세 글자가 필요합니다.

접근 방법 및 알고리즘

이 문제는 그리디(Greedy) 관점에서 매우 간단하게 해결할 수 있습니다. 각 글자가 가질 수 있는 최댓값은 26(z)이므로, 가능한 한 큰 값의 글자를 반복해서 사용하면 글자 수를 최소화할 수 있습니다.

  1. n이 26으로 나누어 떨어지면, 필요한 글자 수는 n / 26입니다.
  2. n이 26으로 나누어 떨어지지 않으면, 나머지 값을 표현하기 위해 글자가 하나 더 필요하므로 답은 (n / 26) + 1입니다.

즉, 올림 나눗셈(ceil division)을 활용하면 다음과 같이 표현할 수도 있습니다.

답 = ceil(n / 26) = (n + 25) / 26

C++ 구현 예제

#include <iostream>
using namespace std;

int minRequiredSets(int n){
    if (n % 26 == 0) {
        return (n / 26);
    } else {
        return (n / 26) + 1;
    }
}

int main(){
    int n = 72;
    cout << "Minimum required sets: " << minRequiredSets(n) << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Minimum required sets: 3

코드 설명

minRequiredSets 함수는 입력받은 정수 n에 대해 나머지 연산자(%)를 사용해 26으로 나누어 떨어지는지 확인합니다. 나누어 떨어진다면 몫(n / 26)이 곧 필요한 최소 글자 수이며, 그렇지 않다면 몫에 1을 더한 값을 반환합니다. 시간 복잡도는 O(1)로, 어떤 크기의 입력에도 즉시 결과를 계산할 수 있습니다.