[C++][백준][알고리즘] 나머지 연산 🎯

10430번

10430번: 나머지

덧셈, 곱셉, 뺄셈에서는 다음과 같은 식을 성립합니다. (나머지는 불가능)

• (A+B) mod M = ((A mod M) + (B mod M)) mod M
  • (4 + 7) % 3 = 11 % 3 = 2
  • (4 % 3 + 7 % 3) = (1 + 1) % 3 = 2
• (A×B) mod M = ((A mod M) × (B mod M)) mod M
  • (4 * 7) % 3 = 28 % 3 = 1
  • (4 % 3 * 7 % 3) = (1 * 1) % 3= 1
• (A-B) mod M = ((A mod M) - (B mod M)) mod M
  • (7 - 3) % 3 = 4 % 3 = 1
  • (7 % 3 - 3 % 3) = (1 - 0) % 3 = 1
• 단, 뺄셈에서는 프로그래밍 언어에 따라 부호가 다르게 나옵니다. C++은 음수를 지원합니다.
  • (6 % 3 ‒ 5 % 3) % 3 = (0 ‒ 2) % 3 = -2 % 3 = -2?

 

4375번

4375번: 1

나머지 연산이 포함된 문제는 다음과 같은 고려할 사항이 있습니다.

• 수의 크기가 int,longlong의 범위를 넘어갈 수 있기 때문에, 수를 실제로 만들 수 없다.
• Java의 BigInteger,Python은 수의 범위 제한이 없어서 수를 실제로 만들 수 있지만, 수의 크기가 커지면 나누는데 걸리는 시간도 매우 오래 걸린다.

 

틀린 코드

#include <iostream>

int main() {
    int n;
    
    while(scanf("%d", &n) != EOF)
    {
        int digit = 1;
        long long value = 1;
        
        while(true)
        {
            value *= 10;
            value += 1;
            ++digit;
            
            if(value % n == 0)
            {
                printf("%d\n", digit);
                break;
            }
        }
    }

    return 0;
}

• 가장 먼저 생각할 수 있는 방법으로, 단순히 실제 value의 값을 1111111... 처럼 늘려 mod 연산이 0이 나올때까지 반복하여 계산할 수 있습니다. 하지만 이 방법은 시간 초과가 나 더 효율적인 방법을 찾아야 했습니다.

 

정답 코드

#include <iostream>

int main() {
    int n;
    
    while(scanf("%d", &n) != EOF)
    {
        int digit = 0; // 자리 수
        int remains = 1 % n; // 나머지
        
        while(true)
        {
            /*
                1 % 3 = 1
                11 % 3 = (1 * 10 + 1) % 3 = ({1 % 3} * 10 + 1) % 3
                111 % 3 = (11 * 10 + 1) % 3 = ({11 % 3} * 10 + 1) % 3
                1111 % 3 = (111 * 10 + 1) % 3 = ({111 % 3} * 10 + 1) % 3
                
                규칙: 이전 계산 값의 나머지 값을 활용하면 수가 무수히
                커지지 않고 계산할 수 있음!
            */
            
            // 나머지 연산의 성질을 이용한 식
            int remains = (remains * 10 + 1) % n;
            ++digit;
            
            if(remains == 0)
            {
                printf("%d\n", digit);
                break;
            }
        }
    }

    return 0;
}

• 나머지 연산자의 성질을 이용한 방법으로 해결하였습니다.
  • 1 % 3 = 1
  • 11 % 3 = (1 * 10 + 1) % 3 = ({1 % 3} * 10 + 1) % 3
  • 111 % 3 = (11 * 10 + 1) % 3 = ({11 % 3} * 10 + 1) % 3
  • 1111 % 3 = (111 * 10 + 1) % 3 = ({111 % 3} * 10 + 1) % 3
• 위 식과 같이 식을 분해하면 이전 값을 활용하여 수가 커지지 않고 계산을 이어나갈 수 있습니다.
• 예를 들어, 1이 10000자리인 매우 큰 수의 나머지가 3이라고 하였을때, 10001자리는 다음과 같이 구할 수 있습니다.
  • (3 * 10 + 1) % N