cadenzah   4년 전

29.5번 어린이날 문제 풀이에 보면 이런 내용이 있습니다.

...

14장에서 소개했던 나머지 연산의 분배 법칙을 기억하신다면, 3번 조건을 만족하는 수를 하나하나 만들면서 그 중 2번 조건을 만족하는 수를 걸러내기란 어렵지 않음을 아실 겁니다. c를 앞에서부터 한자리씩 만들어갈 때, 지금까지 만든 c의 뒤에 숫자 x를 붙인 결과인 c * 10 + x를 n으로 나눈 나머지는 실제 c를 모르더라도 알 수 있습니다. 다음과 같은 성질이 성립하기 때문입니다.

```

((c mod n) * 10 + x) mod n = (c * 10 + x) mod n

```

따라서 한 자리 씩 c를 만들어 갈 때 중요한 것은 현재 숫자가 아니라 c를 n으로 나눈 나머지가 됩니다. 이 점을 이용하면 n으로 나눈 나머지가 m인 최소 숫자를 쉽게 찾을 수 있습니다.

...

위 설명인데요, c를 몰라도 알 수 있다는 것이 이해가 안 됩니다. 설명해주실 수 있는 분 계신가요? 미리 감사드립니다. (14장의 모듈라 연산 관련된 부분은 읽었습니다)

sait2000   4년 전

c는 모르지만 c mod n은 알고있다는 뜻일 겁니다.

Green55   4년 전

"지금까지 만든 c의 뒤에 숫자 x를 붙인 결과인 c * 10 + x를 n으로 나눈 나머지" 는

식으로 표현하면 (c * 10 + x) mod n 이고,

이는 ((c mod n) * 10 + x) mod n와 같기 때문에

매우 큰 실제 c의 값을 몰라도, c를 n으로 나눈 나머지(c mod n)만 관리하면 된다는 뜻 같습니다.

cadenzah   4년 전

흠... 제가 나머지 연산의 분배법칙에 대해서 제대로 이해를 못한거같아요. 두분 모두 답변 감사합니다

댓글을 작성하려면 로그인해야 합니다.