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

C++로 N을 회문의 합으로 표현하는 데 필요한 최소 회문 개수 구하기

문제 정의

하나의 숫자 N이 주어졌을 때, N을 여러 개의 회문(Palindrome)의 합으로 표현하기 위해 필요한 최소한의 회문 개수를 구하는 것이 목표입니다.

회문이란 앞에서 읽으나 뒤에서 읽으나 같은 숫자를 의미합니다. 예를 들어 7, 8, 11, 121 등이 모두 회문입니다.

예시: N = 15인 경우, 15 = 8 + 7처럼 두 개의 회문(8과 7)만 있으면 표현할 수 있습니다. 따라서 필요한 최소 회문 개수는 2입니다.

접근 방법 및 알고리즘

이 문제는 크게 두 단계로 나누어 해결할 수 있습니다.

  1. N 이하의 모든 회문을 오름차순으로 생성합니다. 회문은 숫자의 절반을 만든 뒤 나머지 절반을 거울상처럼 뒤집어 붙이는 방식으로 효율적으로 생성할 수 있습니다.
  2. 생성된 회문들 중에서 합이 정확히 N이 되는 가장 작은 부분 집합(subset)의 크기를 찾습니다. 이 과정은 동적 계획법(DP)과 메모이제이션을 활용하여 중복 계산을 피하고 효율성을 높입니다.

C++ 구현 예제

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;

vector<vector<long long>> table;

// 입력값을 받아 홀수/짝수 길이의 회문을 생성하는 함수
int createPalindrome(int input, bool isOdd){
    int n = input;
    int palindrome = input;
    if (isOdd)
        n /= 10;
    while (n > 0) {
        palindrome = palindrome * 10 + (n % 10);
        n /= 10;
    }
    return palindrome;
}

// n 이하의 모든 회문을 생성하여 벡터로 반환
vector<int> generatePalindromes(int n){
    vector<int> palindromes;
    int number;
    for (int j = 0; j < 2; j++) {
        int i = 1;
        while ((number = createPalindrome(i++, j)) <= n)
            palindromes.push_back(number);
    }
    return palindromes;
}

// 재귀 + 메모이제이션으로 최소 부분 집합 크기 계산
long long minSubsetSize(vector<int>& vec, int i, int j, int n){
    if (n == 0)
        return 0;
    if (i > j || vec[i] > n)
        return INT_MAX;
    if (table[i][n])
        return table[i][n];
    table[i][n] = min(1 + minSubsetSize(vec, i + 1, j, n - vec[i]),
                      minSubsetSize(vec, i + 1, j, n));
    return table[i][n];
}

// 전체 흐름: 회문 생성 → 정렬 → DP 테이블 초기화 → 최솟값 반환
int requiredPalindromes(int n){
    vector<int> palindromes = generatePalindromes(n);
    sort(palindromes.begin(), palindromes.end());
    table = vector<vector<long long>>(palindromes.size(),
            vector<long long>(n + 1, 0));
    return minSubsetSize(palindromes, 0, palindromes.size() - 1, n);
}

int main(){
    int n = 15;
    cout << "Minimum required palindromes = " <<
        requiredPalindromes(n) << endl;
    return 0;
}

코드 설명

  • createPalindrome: 기준 숫자의 절반을 이용해 홀수 자릿수 또는 짝수 자릿수 회문을 만듭니다. 숫자를 한 자리씩 뒤집어 뒤에 붙이는 방식으로 동작합니다.
  • generatePalindromes: 짝수 길이와 홀수 길이 회문을 각각 생성하여 N 이하인 것들을 모두 수집합니다.
  • minSubsetSize: 각 회문을 선택하거나 선택하지 않는 두 가지 경우를 재귀적으로 탐색하며, 이미 계산된 결과는 DP 테이블(table)에 저장해 재사용합니다.

실행 결과

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

Minimum required palindromes = 2

N = 15일 때 8과 7이라는 두 개의 회문으로 15를 표현할 수 있으므로, 결과값 2가 올바르게 출력되는 것을 확인할 수 있습니다.