C++에서 힘 P로 처치할 수 있는 최대 인원 수 구하기

문제 개요

이 문제는 주어진 힘(strength) P로 최대 몇 명까지 처치할 수 있는지 구하는 것이 목표입니다.

무한히 많은 사람들이 한 줄로 서 있고, 각 사람에게는 1부터 시작하는 번호(index)가 붙어 있습니다. s번째 사람의 힘은 s²이며, 힘이 s인 사람을 처치하면 자신의 힘도 s만큼 감소합니다.

예제를 통해 문제를 자세히 살펴보겠습니다.

입력

P = 20

출력

3

풀이 과정

1번째 사람의 힘 = 1 × 1 = 1 < 20 → 처치 가능
남은 힘 = 20 − 1 = 19
2번째 사람의 힘 = 2 × 2 = 4 < 19 → 처치 가능
남은 힘 = 19 − 4 = 15
3번째 사람의 힘 = 3 × 3 = 9 < 15 → 처치 가능
남은 힘 = 15 − 9 = 6
4번째 사람의 힘 = 4 × 4 = 16 > 6 → 처치 불가능
정답 = 3

같은 방식으로 P = 30이 입력되면 1 + 4 + 9 + 16 = 30이므로 네 번째 사람까지 처치할 수 있어 정답은 4가 됩니다.

알고리즘 접근 방식

• main() 함수: 힘을 저장할 int형 변수 P를 30으로 초기화한 뒤 Max() 함수에 전달합니다.
• Max() 함수: 누적 힘 s와 정답 카운터 ans를 int형으로 선언하고 0으로 초기화합니다.
• j = 1부터 시작하여 j × j ≤ P를 만족하는 동안 반복문을 실행합니다.
• 반복문 내부에서 s에 j × j를 더한 뒤, s ≤ P이면 ans를 1 증가시키고, 조건을 벗어나면 break로 반복을 종료합니다.
• 모든 처리가 끝나면 ans를 반환합니다.

핵심 아이디어는 1² + 2² + 3² + … 처럼 제곱수를 순서대로 더해가며 P를 초과하지 않는 최대 항의 개수를 세는 그리디(greedy) 방식입니다. 시간 복잡도는 O(√P)로 매우 효율적입니다.

C++ 구현 코드

#include <bits/stdc++.h>
using namespace std;
int Max(int P){
    int s = 0, ans = 0;
    for (int j = 1; j * j <= P; j++){
        s = s + (j * j);
        if (s <= P)
            ans++;
        else
            break;
    }
    return ans;
}
// 메인 함수
int main(){
    // 힘
    int P = 30;
    cout << "힘 P로 처치할 수 있는 최대 인원 수: " << Max(P);
    return 0;
}

실행 결과

힘 P로 처치할 수 있는 최대 인원 수: 4