nstalways   3년 전

주어진 문제를 그대로 구현했을 때, 시간 초과가 발생했었습니다.

왜 그런가 생각해보니, 특정 숫자의 경우의 수 값이 너무 크다 보니 발생하는 건가 싶었습니다.

그래서 dp 배열에 값을 저장할 때 1000000009로 나눈 나머지 값을 저장하니 문제 없이 통과할 수 있었습니다.

그러다 한 가지 의문이 들었습니다.

숫자 n을 1, 2, 3으로 표현할 수 있는 경우의 수를 1000000009로 나눈 나머지를 출력하라는 건 이해가 가는데,

그렇게 하기 위해선 이전 숫자들의 경우의 수를 저장할 때도 1000000009로 나눈 나머지를 저장해야 한다는 것이 이해가 가지 않았습니다.

조금 생각해보니, 분배 법칙이 떠올랐는데요.

예를 들어서, a + b + c = d라는 수식이 있다고 해봅시다.

그리고 1000000009를 k라고 해봅시다.

문제에서 요구하는 것은 (d % k)인데요.

앞선 수식에 따라 d = a + b + c 이기 때문에 ((a + b + c) % k)로 표현할 수 있습니다.

이를 분배 법칙에 따라서 풀어보면 (a % k) + (b % k) + (c % k) = (d % k)로 나타낼 수 있습니다.

따라서 이전 값들을 k로 나눈 나머지를 모두 합했을 때, d를 k로 나눈 나머지와 같다는 것을 알 수 있었습니다.

주의할 것은 어디에 초점을 두는가에 따라 분배 법칙이 성립하지 않을 수도 있다는 점입니다 (올바른 표현인지는 모르겠습니다).

예를 들어, 5 % (2 + 3) 에서는 분배 법칙이 성립하지 않습니다.

5 % (2 + 3) = 5 % 5 = 0

(5 % 2) + (5 % 3) = 1 + 2 = 3

0 != 3 >> 성립하지 않음

하지만 (2 + 3) % 5에서는 분배 법칙이 성립합니다.

(2 + 3) % 5 = 5 % 5 = 0

(2 % 5) + (3 % 5) = 0 + 0 = 0

0 == 0 >> 성립

더 깊게 파면 보다 확실한 증명이 있을 듯 한데, 지식의 한계로 여기까지만 정리해보았습니다.

혹시 잘못된 정보나 보완해야 할 정보가 있다면, 추가해주시면 감사하겠습니다.

참고한 링크입니다, 감사합니다.

https://www.quora.com/Is-modul...

alsrjs0725   3년 전

더하기 뿐만 아니라 곱하기, 빼기에서도 성립하는 성질이니 공부 하시면 좋을것같아요

관련 글은 링크 남깁니다

protarie   3년 전

연산자의 입장에서 보면 분배법칙이라고 부를 수도 있지만,

모듈러 연산의 성질이라고 하는 것이 더 올바른 표현이라고 할 수 있습니다.

수론(Number theory)에서 엄밀한 정의와 증명을 다룹니다.

수학에 흥미가 있으시다면, 관련 입문 서적을 읽어보는 것도 좋습니다.

대학교 교재로 사용되는 것 중에도 쉬운 것들이 많이 있습니다.

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