문제 개요
세 개의 정수 a, b, limit가 주어졌을 때, [a, limit] 범위 내에 속하는 수들 중에서 특정 형태로 표현되는 숫자들을 찾아 출력하는 것이 이번 문제의 목표입니다. 이러한 숫자들을 강력한 정수(Powerful Integers)라고 부르며, 다음과 같이 정의합니다.
aⁱ + bʲ (단, i ≥ 0 이고 j ≥ 0)
예시로 이해하기
입력:
a = 2
b = 5
limit = 10
출력:
[2, 3, 5, 6, 7, 9]
설명: 가능한 모든 지수 조합(i, j)에 대해 계산하면 다음과 같습니다.
- 2⁰ + 5⁰ = 2 / 2⁰ + 5¹ = 6
- 2¹ + 5⁰ = 3 / 2¹ + 5¹ = 7
- 2² + 5⁰ = 5 / 2² + 5¹ = 9
- 2³ + 5⁰ = 9 (중복 값은 한 번만 저장)
따라서 최종 결과는 [2, 3, 5, 6, 7, 9]가 됩니다.
문제 해결 접근 방식
이 문제는 브루트 포스(Brute Force) 기법으로 손쉽게 해결할 수 있습니다. 두 개의 중첩 반복문을 사용해 a의 거듭제곱과 b의 거듭제곱을 순회하면서, 두 값의 합이 limit 이하이면 집합(set)에 저장하는 방식입니다. set 자료구조를 활용하면 중복된 값이 자동으로 제거되고 오름차순으로 정렬된다는 큰 장점이 있습니다.
알고리즘 단계
- 세 개의 입력값 a, b, limit을 받습니다.
- powerfulNumbers(int a, int b, int limit) 함수는 a, b, limit을 입력으로 받아, aⁱ + bʲ (i ≥ 0, j ≥ 0) 형태로 표현되는 모든 강력한 정수의 목록을 반환합니다.
- limit까지 순회하는 두 개의 중첩 반복문을 사용하여, 매 반복마다 거듭제곱 값을 누적으로 곱해 나가며 강력한 정수를 찾습니다.
- 계산된 수가 [a, limit] 범위에 속한다면 set에 저장합니다(중복 방지).
- 마지막으로 set을 순회하며 결과를 출력합니다.
C++ 구현 코드
#include <bits/stdc++.h>
using namespace std;
void powerfulNum(int a, int b, int limit) {
set<int> s;
for (int i = 1; i < limit; i *= a) {
for (int j = 1; j < limit; j *= b) {
if (i + j <= limit) {
s.insert(i + j);
} else break;
if (b == 1) break;
}
if (a == 1) break;
}
for (auto it : s) {
cout << it << " ";
}
}
int main() {
int a = 2;
int b = 5;
int limit = 10;
powerfulNum(a, b, limit);
return 0;
}
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
실행 결과
2 3 5 6 7 9
결과를 통해 2부터 10 사이의 강력한 정수가 [2, 3, 5, 6, 7, 9]임을 확인할 수 있습니다.
복잡도 분석
- 시간 복잡도: O(logₐ(limit) × log_b(limit)) — a와 b의 거듭제곱이 limit을 초과하지 않을 때까지만 반복하므로 매우 효율적입니다.
- 공간 복잡도: O(N) — 결과값을 저장하는 set에 필요한 공간입니다.
참고로 코드에서 a == 1 또는 b == 1인 경우 거듭제곱 값이 증가하지 않아 무한 루프에 빠질 수 있으므로, 이를 방지하기 위한 break 조건이 포함되어 있습니다. 이처럼 경계 조건(엣지 케이스)을 꼼꼼하게 처리하는 것이 견고한 코드를 작성하는 핵심입니다.