p223 바닥 공사 796,796에 대한 질문입니다.

[JeonSoongu]

안녕하십니까, 동빈님. 이것이 코딩테스트다를 보면서 공부하고 있는 학생입니다. 정말 기초적인 것이지만, 꼭 이해하고 싶은 부분이 있어서 개인적으로 공부하다가 질문을 남기게 됐습니다.

동적프로그래밍의 "(4) 바닥공사" 문제 파트입니다. 2 x N 크기의 바닥을 채우는 방법의 수를 "796,796" 이라는 수로 나눠주고 있는데, 여기서 "796,796"에 관련된 질문입니다.

코드를 보니,

d[i] = (d[i - 1] + 2 * d[i - 2]) % 796796

위 처럼 매 연산마다 796796을 나눠주더라구요. 제 생각에는 매번 이렇게 % 연산을 했을 때의 **d[n]**의 결과값과 % 연산을 하지않고 최종 d[n] 값에 796,796을 나눈 값이 다를 것이라 생각했습니다.

그런데 결과 값이 동일하게 나오더군요. 도대체.. 어떻게 결과 값이 같게 나올 수 있는건지 이해가 안되더라구요. 796,796이 아닌 어떤 수로 나누던지 결과는 같게 나오던데, 이에 대한 이유를 알 수 있을까요?

[ohjayho]

저도 그 부분이 궁금했는데. 수학적으로 (a+b)%X = ((a%X) + (b%X)) % X 라고 합니다. 나머지 연산의 분배 법칙으로 검색해보시면 도움되실겁니다. 백준 10430번 문제도 참고해보세요. https://www.acmicpc.net/problem/10430

[young-hun-jo]

저도 궁금했는데, 답변 달아주신 분, 질문해주신 분 감사합니다!