C++에서 합이 S가 되도록 하는 최소 숫자 개수 구하기

문제 설명

1부터 N까지의 숫자와 하나의 정수 S가 주어집니다. 이때 주어진 숫자들을 더하여 합이 정확히 S가 되도록 만들 때, 필요한 숫자 개수의 최솟값을 구하는 것이 문제입니다.

예시

예를 들어 n = 7, s = 10이라면 단 두 개의 숫자만으로 10을 만들 수 있습니다.

(7, 3)
(6, 4)
(5, 5)

사용하는 숫자의 개수를 최소화하려면 가능한 한 큰 값을 우선적으로 선택해야 합니다. 즉, 가장 큰 숫자인 N을 먼저 더하고, 남은 합은 다시 N 이하의 숫자로 채워 나가면 됩니다.

알고리즘

정답은 아래 공식으로 간단하게 계산할 수 있습니다.

S % N > 0 이면   답 = (S / N) + 1
S % N == 0 이면 답 = S / N

즉, S를 N으로 나누었을 때 나머지가 존재하면 몫에 1을 더하고, 나누어떨어지면 몫이 곧 정답입니다. 이는 올림 나눗셈(ceiling division)과 동일한 원리입니다. 예를 들어 S = 10, N = 7인 경우 7을 하나 사용하고 남은 3을 한 번 더하면 되므로 정답은 2가 됩니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;

int getMinNumbers(int n, int s)
{
    // 올림 나눗셈: 나머지가 있으면 몫에 1을 더한다
    return s % n ? s / n + 1 : s / n;
}

int main()
{
    int n = 7;
    int s = 10;
    cout << "필요한 최소 숫자 개수 = " << getMinNumbers(n, s) << endl;
    return 0;
}

위 프로그램을 컴파일하여 실행하면 다음과 같은 결과가 출력됩니다.

출력

필요한 최소 숫자 개수 = 2

복잡도

단 한 번의 나눗셈 연산으로 정답을 구하므로 시간 복잡도는 O(1)이며, 추가적인 메모리를 사용하지 않으므로 공간 복잡도 역시 O(1)입니다.