Tip - 특정 값의 나머지의 초과 여부 결정

March 16, 2023

나머지가 $m$을 초과했는 지 검사

어떤 문제에서 구하려는 정답이 매우 커질 수 있어서 나머지 $m$ 으로 나눈값을 출력하라고 하는 문제는 흔하다.

하지만 그 정답이 $m$ 이상의 값이 되어서 나눠진건지 아니면 원래 $m$ 미만이라서 그 값인건지를 검사하는 것은 어떻게할까?

실제로 이런걸 물어보는 문제가 간혹 등장한다.

예를 들어, $a+b$ 를 구하고 있다고 하자.

바로 연산의 값이 $mod$ 이상이 나올 때, $k \equiv a+b~(mod~m)$ 을 만족하는 $k$를 그대로 저장하는게 아니라 $k+m$ 을 저장하는 것이다.

그러면 한 번이라도 $m$ 값 이상이 된 적이 있는 값이라면 $m\sim 2m-1$ 의 값을 담게 될 것이고, 그렇지 못한 값이라면 $0 \sim m-1$ 의 값을 가지게 될 것이므로 구분이 된다.

일단 문제는 knapsack dp이다.

$dp[i]=$ 합쳐서 $i$ 를 만드는 경우의 수 라고 할 때, $dp[i]$ 값이 0인지 아닌지가 중요한 문제이다.

왜냐면 $i$와 $\sum_v - i$ 이 둘다 0이 아니여야 두 수를 만드는 방법이 모두 존재해 차이를 정답에 min 연산 해줄 수 있기 때문이다.

$i$가 $0$이 아니면 당연히 $\sum_v -i \ne 0$ 이다.

그런데 여기서 나머지연산을 그대로 해버리면 $1,000,000$이 딱 나왔을 때 그게 $0$으로 저장이 되어버려 문제를 올바르게 해결할 수 없다.