개념
정수 X가 주어졌을 때, 처음 N개의 자연수의 제곱의 합이 X를 초과하지 않도록 하는 최댓값 N을 구하는 것이 이 문제의 목표입니다.
입력
X = 7
출력
2
N = 3일 경우 수열의 합이 X를 초과하므로(1² + 2² + 3² = 1 + 4 + 9 = 14), 2가 N이 가질 수 있는 최댓값입니다.
입력
X = 27
출력
3
N = 4일 경우 수열의 합이 X를 초과하므로(1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30), 3이 N이 가질 수 있는 최댓값입니다.
풀이 방법
단순 해법
가장 간단한 방법은 S(N) ≤ X를 만족하는 최대 N까지 1부터 반복문을 실행하는 것입니다. 여기서 S(N)은 처음 N개의 자연수의 제곱의 합을 의미하며, 다음 공식으로 바로 계산할 수 있습니다.
S(N) = N × (N + 1) × (2 × N + 1) / 6
이 방법의 시간 복잡도는 O(N)입니다.
효율적인 해법: 이진 탐색
이진 탐색(Binary Search)을 활용하면 더 효율적으로 문제를 해결할 수 있습니다. 제곱의 합 S(N)은 N이 커질수록 단조 증가하므로 이진 탐색을 적용하기에 적합하며, 알고리즘은 다음과 같이 단계별로 진행됩니다.
탐색 범위의 양 끝을 low와 high로 설정하고, 중간값 mid를 (low + high) / 2로 계산합니다.
mid까지의 제곱의 합이 X 이하라면, 조건을 만족하는 더 큰 N이 존재할 수 있으므로 답을 mid로 갱신하고 low를 mid + 1로 이동합니다.
반대로 합이 X를 초과한다면, high를 mid - 1로 이동하여 탐색 범위를 줄입니다.
이 방법의 시간 복잡도는 O(log N)으로, 단순 반복문 방식보다 훨씬 빠르게 동작합니다.
예제 코드
// 접근 방법의 C++ 구현
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// 처음 N1개의 자연수의 제곱의 합을 반환하는 함수
ll squareSum(ll N1){
ll sum1 = (ll)(N1 * (N1 + 1) * (2 * N1 + 1)) / 6;
return sum1;
}
// 처음 N개의 자연수의 제곱의 합이
// X를 넘지 않는 최대 N을 반환하는 함수
ll findMaxN(ll X){
ll low1 = 1, high1 = 100000;
int N1 = 0;
while (low1 <= high1) {
ll mid1 = (high1 + low1) / 2;
if (squareSum(mid1) <= X) {
N1 = mid1;
low1 = mid1 + 1;
}
else
high1 = mid1 - 1;
}
return N1;
}
// 드라이버 코드
int main(){
ll X = 27;
cout << findMaxN(X);
return 0;
}출력
3
X = 27이 입력되면 squareSum(3) = 14 ≤ 27이지만 squareSum(4) = 30 > 27이므로, 프로그램은 조건을 만족하는 최댓값인 3을 출력합니다.