[구름LEVEL] 어려운 문제

난이도	정답률
★★	69.5%

 

구름LEVEL

문제

정수 N이 주어질때 N!을 구하여 만들어진 숫자가 두 자리 이상이면 한 자리가 될 때까지 자릿수를 더한 값을 출력한다.

0 ≤ N ≤ 10000

해결

key point, int의 범위가 넘어가는 N!을 계산하기 위하여 각 자릿수를 배열에 저장시킨다.

1. 각 자릿수를 저장할 배열을 v라고한다. 수가 123이라면 v[0]=3, v[1]=2, v[1] 처럼 역순으로 저장한다.
2. 일단 1부터 N까지 곱하여 N!을 구해야하므로 v배열에 1을 넣어준다. → 여태까지 구한 숫자가 v가 됨.
3. 2부터 N까지 변수 i를 사용하여 반복문을 돌리면서 v의 각 자릿수 v[j](변수 j활용)에 i를 곱해준다.
4. 곱한 값을 r이라고 할 때 r을 10으로 나눈 나머지(=일의 자리 수)를 j번째 수로 저장한다.
5. 다시 r을 10으로 나눈 수가 올림수가되어 j+1번째에 활용된다.
6. v의 각 자릿수에 i를 모두 곱했는데 올림수 r이 있다면 v.push_back(r%10)을 활용하여 추가해준다.
7. 이렇게 i가 N일 때 까지 반복하여 v에 모든 수를 저장했다면
8. 각각 자릿수를 더할 때도 같은 방법을 활용하여 더하여 출력한다.

처음에 어떻게 해야할지 고민을 하다가 결국 검색을 통해서 알게 되었는데, 아래 블로그가 도움이 많이 됐다. 하지만 아직도 많이 헷갈리고^^.. 더 많은 문제를 풀어봐야 완전히 내게 될 것 같다.

[C/C++]어떻게 큰 수(100만이상)의 팩토리얼값을 구 할 수 있을까?

 

코드

#include <iostream>
#include <vector>
using namespace std;
int n, i, j, r, ans;
vector<int> v;
int main() {
    scanf("%d", &n);
    v.push_back(1);
    for (i = 2; i <= n; i++) {
        j = 0;
        while (!v[j]) j++;
        for (r = 0 ; j < v.size(); j++) {
            r += v[j] * i; // r = v[j] * i + r;
            v[j] = r % 10; // push_back()하면 무한루프.
            r /= 10;
        }
        while (r) {
            v.push_back(r % 10);
            r /= 10;
        }
    }
 
    for (i = 0, r = 0; i < v.size(); i++) {
        if (!v[i]) continue;
        r += ans + v[i];
        ans = r % 10;
        r /= 10;
    }
    while (r) {
        ans += r % 10;
        r /= 10;
    }
    printf("%d", ans);
    return 0;
}