프로그래머스 입문 120848 팩토리얼

2026. 07. 11

문제

정수 n이 주어질 때, i! <= n을 만족하는 가장 큰 정수 i를 구하시오.

i	i!
1	1
2	2
3	6
4	24
5	120
6	720
7	5040
8	40320
9	362880
10	3628800

n	result
1	1
2	2
7	3
3628800	10

n이 1이면 1!(1) <= n < 2!(2)가 성립한다.
따라서 조건을 만족하는 가장 큰 정수는 1이다.

n이 2이면 2!(2) <= n < 3!(6)이 성립한다.
따라서 조건을 만족하는 가장 큰 정수는 2이다.

n이 7이면 3!(6) <= n < 4!(24)가 성립한다.
따라서 조건을 만족하는 가장 큰 정수는 3이다.

n이 3,628,800이면 10!(3628800) <= n < 11!(39916800)이 성립한다.
따라서 조건을 만족하는 가장 큰 정수는 10이다.

풀이

초과하는 팩토리얼 찾기

int solution(int n)
{
    int i = 1;
    int factorial = 1;

    while (factorial <= n)
    {
        i++;
        factorial *= i;
    }

    return i - 1;
}

문제의 조건 i! <= n을 반대로 생각하면, 팩토리얼을 계속 키우다가 처음으로 n을 초과하는 순간, 즉 i! > n이 되는 지점을 찾으면 된다.
예를 들어 n이 7이라면 1! = 1, 2! = 2, 3! = 6은 모두 7 이하이다.
다음 값인 4! = 24는 7보다 크므로, 4 - 1인 3을 반환하면 된다.

i는 현재 팩토리얼을 만들 때 곱할 숫자를 나타내며, factorial은 현재까지 만든 팩토리얼 값이다.
처음에는 1!을 의미하도록 둘 다 1로 시작한다.

반복문 안에서는 현재 팩토리얼 값이 아직 n 이하일 때마다 다음 번호의 팩토리얼 값을 만든다.
그래서 다음 검사에서는 한 단계 더 큰 팩토리얼이 n을 초과하는지 확인할 수 있다.

반복문이 끝났다는 것은 factorial > n이 되었다는 뜻이다.
이때의 i는 처음으로 n을 초과한 팩토리얼의 번호이므로, 조건을 만족하는 마지막 번호인 i - 1을 반환한다.

n을 나누며 확인하기

int solution(int n)
{
    int remaining = n;
    int result = 1;
    int divisor = 2;

    while (remaining >= divisor)
    {
        remaining /= divisor;
        result++;
        divisor++;
    }

    return result;
}

문제에서 주어진 조건 i! <= n은 1 * 2 * 3 * ... * i <= n으로 풀어 쓸 수 있다.

팩토리얼을 직접 곱해 가는 대신, n을 2, 3, 4 순서로 나누며 어디까지 조건이 성립하는지 확인할 수 있다.
나눗셈이 가능할 때마다 그 수까지의 팩토리얼이 n 이하라고 판단한다.

예를 들어 처음 n이 7이면 먼저 2로 나눌 수 있으므로 2! <= 7이 성립하고, remaining은 7 / 2의 몫인 3이 된다.
이제 remaining은 3이고 3으로 나눌 수 있으므로 3! <= 7이 성립하고, remaining은 3 / 3의 몫인 1이 된다.
그다음에는 remaining이 1이라 4로 나눌 수 없으므로 4! <= 7은 성립하지 않는다.
따라서 조건을 만족하는 가장 큰 정수는 3이다.

result는 현재까지 만들 수 있는 것으로 확인한 팩토리얼의 번호다.
remaining은 나누어 가며 조건을 확인할 값이다.
divisor는 다음에 나눌 수를 의미한다.

반복문의 조건식은 n % divisor == 0이 아니다.
C의 정수 나눗셈은 나누어떨어지지 않아도 몫만 남으므로, remaining >= divisor이면 remaining /= divisor를 수행할 수 있다.

미리 구한 팩토리얼과 비교하기

int solution(int n)
{
    const int factorials[] = {1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800};
    int last_index = sizeof(factorials) / sizeof(factorials[0]) - 1;

    for (int i = last_index; i >= 0; i--)
    {
        if (factorials[i] <= n)
        {
            return i + 1;
        }
    }

    return 1;
}

이 문제에서 n의 범위는 1!(1) <= n <= 10!(3628800)이다.
따라서 1!부터 10!까지의 값을 배열에 미리 저장해 두고, 가장 큰 값부터 차례대로 n 이하인지 검사할 수 있다.
큰 값부터 확인하므로 처음으로 조건을 만족하는 위치가 정답에 해당한다.

배열의 0번 인덱스에는 1!, 1번 인덱스에는 2!가 들어 있다.
즉 factorials[i]가 의미하는 팩토리얼 번호는 i + 1이므로, 조건을 만족하면 i + 1을 반환한다.