글 읽기 - MOD연산과 관련해서 DP질문 드립니다. 왜 맞았는지 모르겠습니다

20rnjsekdns 2년 전 0

문제를 풀면서 결과에서만 15746 나머지 연산을 해주려니 너무 값이 큰 거 같아서 아무 생각 없이 MOD연산의 특징을 활용해서 풀었는데 왜 정답이 되었는지 모르겠습니다.

예를 들어 n이 100일 때의 값이 15747이고, 101이 15748이면 102를 구할 때, 그 값이 3이 되어버리는데 이게 왜 정답인지 잘 모르겠습니다.

#include <iostream>
#include <vector>
#define ll long long
using namespace std;

ll cache[1000001] = { 0, };

int main() {
	int n;
	cin >> n;
	cache[1] = 1;
	cache[2] = 2;
	for (int i = 3; i <= n; i++) {
		cache[i] = (cache[i - 1] % 15746 + cache[i - 2] % 15746) % 15746;
	}
	cout << cache[n];
	return 0;
}

lcr7324 2년 전 2

a = p_a * x + q_a

b = p_b * x _ q_b

라고 두면

(a + b) mod x = (p_a * x + q_a + p_b * x + q_b) mod x = (q_a + q_b) mod x가 됩니다.

덧셈을 아무리 반복해도 이 성질이 유지되므로 cache의 각 항의 실제 값이 아닌 15746으로 나눈 나머지만 들고 있어도 됩니다.

lcr7324 2년 전 1

오타 수정: b = p_b * x + q_b

kipa00 2년 전 3

나눗셈 정리에 기반합니다. 증명은 따로 하지 않겠지만, 다음을 의미합니다: 정수 a와 [0이 아닌 정수 b]에 대해 a = bq + r인 정수 q와 [0 ≤ r < |b|인 정수 r]은 유일하게 존재한다.

이 정리가 있어야 "나머지"가 유일하게 정의되고 따라서 "a를 b로 나눈 나머지" 같은 표현을 쓸 수 있습니다.

다음을 증명합시다:

1 ≤ n이면 cache[n]은 a₁ = 1, a₂ = 2, a_n = a_n-1 + a_n-2로 정의된 수열 {a_n}에 대해 a_n을 N = 15746으로 나눈 나머지이다.

n에 대한 수학적 귀납법을 이용합니다. n = 1, n = 2인 경우 자명하게 성립합니다.

이제 n인 경우를 증명하기 위해 1 ≤ i < n인 모든 i에 대해 주장이 성립한다고 합시다. 그렇다면

a_n-1 = Nq₁ + r₁, a_n-2 = Nq₂ + r₂ (0 ≤ r₁ = cache[n-1] < N, 0 ≤ r₂ = cache[n-2] < N)

로 쓸 수 있습니다.

이때 cache[n]은 r₁ + r₂가 N보다 작으면 r₁ + r₂로 계산됩니다. 그런데

a_n = a_n-1 + a_n-2 = Nq₁ + Nq₂ + r₁ + r₂ = N(q₁ + q₂) + (r₁ + r₂)

이므로 나눗셈 정리에 의해 a_n을 N으로 나눈 나머지는 실제로 (r₁ + r₂)가 됩니다.

만일 r₁ + r₂가 N보다 크거나 같다면 cache[n] = r₁ + r₂ - N으로 계산되는데, 이때도 마찬가지로 나눗셈 정리를 통해 a_n을 N으로 나눈 나머지가 실제로 (r₁ + r₂ - N)임을 증명할 수 있습니다.

20rnjsekdns 2년 전 0

감사합니다 많은 도움이 되었어요!!

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

문제

문제

출처

ICPC

MOD연산과 관련해서 DP질문 드립니다. 왜 맞았는지 모르겠습니다

20rnjsekdns 2년 전 0

lcr7324 2년 전 2

lcr7324 2년 전 1

kipa00 2년 전 3

20rnjsekdns 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말