개념
주어진 숫자 N이 있을 때, 우리의 목표는 N에서 최소한의 자릿수(0개일 수도 있음)를 삭제하여 만들 수 있는 가장 큰 완전세제곱수(perfect cube)를 찾는 것입니다. 주어진 숫자의 어떤 자릿수든 삭제하여 목표 값을 만들 수 있습니다.
어떤 수 A가 임의의 정수 B에 대해 A = B³ 관계를 만족한다면, A를 완전세제곱수라고 부릅니다.
만약 아무리 자릿수를 삭제해도 완전세제곱수를 만들 수 없다면 -1을 출력해야 합니다.
예시
N = 1025인 경우: 숫자에서 0을 삭제하면 125가 남습니다. 125 = 5 × 5 × 5이므로, 이는 5의 세제곱에 해당하는 완전세제곱수입니다.
N = 806인 경우: 0과 6을 차례로 삭제하면 8만 남습니다. 8 = 2 × 2 × 2이므로, 이는 2의 세제곱에 해당하는 완전세제곱수입니다.
접근 방법
주어진 숫자로 만들 수 있는 모든 부분 수열(subsequence)을 검사하여, 각 값이 완전세제곱수인지 확인합니다. 그중 가장 큰 세제곱수를 최댓값으로 유지하며 비교해 나갑니다.
모든 부분 수열은 재귀 호출을 통해 생성할 수 있습니다. 현재 문자열에 각 자릿수를 하나씩 추가하고, 재귀가 반환될 때 마지막 문자를 제거하여 다음 조합을 만드는 방식입니다.
예를 들어 num = "876"이라고 할 때, 각 요소를 현재 문자열에 추가하면 다음과 같은 순서로 부분 수열이 생성됩니다.
8
87
876
이후 재귀가 "87" 상태로 되돌아오면 '7'을 제거하고 다음 반복을 호출하여 부분 수열 "86"을 얻습니다. 이렇게 '8'로 시작하는 모든 경우의 재귀가 끝나면, 이번에는 '7'부터 시작하는 부분 수열 "7", "76"이 생성되고, 마지막으로 "6"까지 탐색을 마칩니다.
결과적으로 이 과정을 통해 주어진 숫자 876의 모든 부분 수열을 빠짐없이 검사할 수 있습니다.
C++ 코드 예제
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll mx1 = INT_MIN;
// 완전세제곱수 여부를 판별하는 함수
bool is_Cube(ll x1) {
if (x1 < 0) return false;
ll r = round(cbrt((double)x1));
return (r * r * r == x1);
}
// 모든 부분 수열을 생성하는 재귀 함수
void printSubSeqRec(string str, int n1, int index = -1, string curr1 = "") {
if (index == n1)
return;
if (!curr1.empty()) {
ll temp = stoll(curr1);
if (is_Cube(temp))
mx1 = max(mx1, temp);
}
for (int i = index + 1; i < n1; i++) {
curr1 += str[i];
printSubSeqRec(str, n1, i, curr1);
curr1.erase(curr1.size() - 1);
}
}
int main() {
int nums1 = 1025;
string str1 = to_string(nums1);
printSubSeqRec(str1, str1.size());
if (mx1 != INT_MIN)
cout << mx1 << endl;
else
cout << "NOT FOUND ANY CUBE" << endl;
return 0;
}
출력 결과
125
복잡도 분석
n자리 숫자의 부분 수열 개수는 최대 2ⁿ개이므로, 전체 시간 복잡도는 대략 O(2ⁿ)입니다. 따라서 이 접근 방식은 자릿수가 많지 않은 입력에 적합합니다. 세제곱수 판별은 cbrt() 함수를 사용해 상수 시간에 처리되므로 전체 성능에 큰 부담을 주지 않습니다.