devhyun46   2년 전

안녕하세요. dp문제를 열심히 풀고 있었는데 %, 나머지 구하는 문제가 많더라고요.

그때마다 풀이들을 보면 %를 틈틈이 해주더라고요. %를 맨마지막에만 하면 뭐 Int가 표현할 수 있는 수를 넘어가서 중간 중간에 계속 해줘야 한다는 그 자체는 이해가 되는데 왜 %를 중간에, 그리고 여러번 해도 괜찮은지 이해가 안갑니다.

예를 들어서 100이라는 수를 7로 나눈다고 하면 나머지가 100 % 7 = 2 입니다.

그런데 100 = 95 + 5 -> 95%7 + 5 %7 =  4 + 5 = 9 이므로 2와 다르게 나옵니다.

마지막 결과에다가 말고 중간에 한번만 해도 이해가 안되는데

많은 문제들이 중간 중간 한번이 아니라 여러번 %를 사용하던데 도대체 왜 괜찮은건가요?


2sungj0   2년 전

최종적으로도 나머지 연산을 한 번 더 해주면

9%7=2인 것 같습니다

djs100201   2년 전

우선 기본적인 모듈려 연산에 대한 공부를 먼저 하셔야 합니다. 

djs100201   2년 전

본문의 근본적인 물음에 대해..
어떤 정수 a를 b로 나눴을때 몫 q 나머지 r은 유일합니다. 즉 유일하게 a=bq+r로 표현됩니다.

이제 두 정수를 더하고 b라는 특정 정수로 나눈 나머지를 더하는 것 두정수를 b로 나누고 더하는것이 동일함을 보이면 됩니다.
a=bq+r 
c=Bq+R이라고 할때
a+c= (b+B)q+r+R입니다.
(a+c) %q= (r+ R)%q
(a%q+c%q)%q= (r+R)%q이므로 동일합니다. 

devhyun46   2년 전

너무 늦게 답변을 드리지만..

명쾌한 설명 감사드립니다!!!

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