10844번 - 쉬운 계단 수
안녕하세요. dp문제를 열심히 풀고 있었는데 %, 나머지 구하는 문제가 많더라고요.
그때마다 풀이들을 보면 %를 틈틈이 해주더라고요. %를 맨마지막에만 하면 뭐 Int가 표현할 수 있는 수를 넘어가서 중간 중간에 계속 해줘야 한다는 그 자체는 이해가 되는데 왜 %를 중간에, 그리고 여러번 해도 괜찮은지 이해가 안갑니다.
예를 들어서 100이라는 수를 7로 나눈다고 하면 나머지가 100 % 7 = 2 입니다.
그런데 100 = 95 + 5 -> 95%7 + 5 %7 = 4 + 5 = 9 이므로 2와 다르게 나옵니다.
마지막 결과에다가 말고 중간에 한번만 해도 이해가 안되는데
많은 문제들이 중간 중간 한번이 아니라 여러번 %를 사용하던데 도대체 왜 괜찮은건가요?
최종적으로도 나머지 연산을 한 번 더 해주면
9%7=2인 것 같습니다
우선 기본적인 모듈려 연산에 대한 공부를 먼저 하셔야 합니다.
https://www.acmicpc.net/proble...
본문의 근본적인 물음에 대해..어떤 정수 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년 전
안녕하세요. dp문제를 열심히 풀고 있었는데 %, 나머지 구하는 문제가 많더라고요.
그때마다 풀이들을 보면 %를 틈틈이 해주더라고요. %를 맨마지막에만 하면 뭐 Int가 표현할 수 있는 수를 넘어가서 중간 중간에 계속 해줘야 한다는 그 자체는 이해가 되는데 왜 %를 중간에, 그리고 여러번 해도 괜찮은지 이해가 안갑니다.
예를 들어서 100이라는 수를 7로 나눈다고 하면 나머지가 100 % 7 = 2 입니다.
그런데 100 = 95 + 5 -> 95%7 + 5 %7 = 4 + 5 = 9 이므로 2와 다르게 나옵니다.
마지막 결과에다가 말고 중간에 한번만 해도 이해가 안되는데
많은 문제들이 중간 중간 한번이 아니라 여러번 %를 사용하던데 도대체 왜 괜찮은건가요?