[Algorithm] Baekjoon 3944번 : 나머지 계산

https://www.acmicpc.net/problem/3944

3944번: 나머지 계산

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int t = 0;
    int b = 0;
    string n;
 
    cin >> t;
 
    for (int i = 0; i < t; i++)
    {
        cin >> b >> n;
        int sum = 0;
 
        for (char& temp : n)
        {
            sum += (temp - '0') % (b - 1);
        }
 
        printf("%d\n", sum % (b - 1));
    }
}

특정 수 n에 대해 몇진법인지 주어졌을 때, n-1진법으로 모듈러연산을 할 줄 알아야 하는 문제.

예를들어 10진수 7829가 주어진다면, 7829 % 9 를  출력해야 한다.

이걸 나머지연산에 의거해서 다시 풀이해보면 아래와 같다. ( A * B ) % P == ( (A%P) * (B%P) ) % P

 

7829 % 9  ==  ( (10^3 * 7)  % 9+ (10^2 * 8) % 9 + (10^1 * 2) % 9 + (10^0 * 9) % 9) % 9 이다.

 

그럼 먼저 (10^3 * 7) % 9  부분을 살펴보자.

1000 * 7을 999 * 7 + 1 * 7  이라고 표현해보자. 

그러면 다시 나머지연산에 의해 아래와 같이 풀이된다.

 

( 1000 * 7 ) % 9 == ( (999 * 7) % 9 + (1 * 7) % 9 ) % 9

 

여기까지 이해했다면 아마 감이 왔을 듯 하다.

(999 * 7) % 9는 0이 되버리기 때문에 결국 자릿수값이였던 7만 남게된다.

이건 10진법뿐만 아니라 다른 진법에도 똑같이 적용된다.

그렇기 때문에 입력으로 주어지는 숫자의 각 자릿수를 b-1진법으로 모듈러 연산을 하고 그 값을 합친다음, 마지막에 한번더 b-1로 모듈러연산을 해주면 된다.

마지막에 한번 더 해줘야하는것을 절대 까먹으면 안된다.

 

3,4년전에 시간초과로 못풀고 남겨뒀었다가 오늘에서야 다시 풀어본다.