[C/C++] 백준 #1769 3의 배수(구현)

이번 문제는 특별한 알고리즘이 있는 것은 아니고, 그냥 지시한대로 구현을 하면 되는 문제입니다.

 

제가 다른 사람들한테 자주 물어본 수학 문제는 이런것이었습니다.

 

1000! (천 팩토리얼)을 계산하면 아주 큰 수가 나올거야.  그 수의 모든 자릿수를 다 더하면, 하나의 수가 되겠지.  이것을 계속 반복하면 결국 한자리 수가 나올텐데, 그 답은?

 

답은 당연하겠지만 9입니다.

 

 

3차리 수라고 하면, \(100a + 10b + c\)로 표현할 수 있습니다.  이것을 다시 분해하면, \(99a + 9b + a + b + c\)로 표현할 수 있죠.  \(10^k - 1 \)은 9의 배수이므로, 주어진 3자리수가 9의 배수이면,  \(a + b + c\)도 9의 배수가 됩니다.  팩토리얼은 6! 부터 9의 배수가 됩니다.  

 

결국 자릿수를 다 더하는 로직을 계산한 것인데, 우선 백만자리가 넘지 않는 수이므로 처음 다 더하면, 최대 수는 9백만이 됩니다.  그러므로 그 다음부터는 int형으로 계산해도 되죠.  9백만이란 숫자이면 7자리이므로 그 다음수는 63 미만의 수가 되죠.  금방 두자리 수자가 되는 것을 알 수 있습니다.  즉, 반복횟수가 극히 짧습니다.

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//-------------------------------------------------
//    baekjoon #1769
//        - by Aubrey Choi
//        - created at 2019-08-09
//-------------------------------------------------
#include <stdio.h>

int main()
{
    int r=0, c=0;
    for(;;c++)
    {
        int ch=getchar();
        if(ch<'0'||ch>'9') break;
        r += ch-'0';
    }
    c=c>1?1:0;
    for(;r>=10;c++)
    {
        int t=0;
        while(r) t+=r%10,r/=10;
        r=t;
    }
    printf("%d\n%s\n",c,r%3?"NO":"YES");
    return 0;
}