인프런 커뮤니티 질문&답변

제 질문은 그게 아니라,

강사님 코드의 두줄을 한줄로 합치면, cnt = ((cnt * 10) + 1)%n 이 됩니다.

이걸 모듈러 연산의 분배법칙을 사용하면,

cnt = ((cnt*10)%n + 1%n)%n 이 되어야 하는게 아닌가 해서요.

근데, 제 코드는 cnt = (cnt * 10) % n + 1%n; 이렇게 %n 이 하나 없는데, 왜 두 코드가 같은 건지 궁금한 겁니다.

cnt = ((cnt * 10) + 1)%n 에서

cnt * 10 을 A라고 하고 1을 B라고 하죠. (A + B) % n 은

A % n + B % n 이겠죠?

이를 치환하면

cnt * 10 % n + 1 % n

이 됩니다.

(A + B) % n = A % n + B % n 이 아니죠,

10 % 2 = 0 이지만, 7 % 2 + 3 % 2 = 2 니까요.

교안에 나와있는 것 처럼 (A + B) % n = (A % n + B % n)%n 이고, 말씀하신 치환대로면

(cnt * 10 % n + 1 % n) %n 이어야 하는거 아닌가요???

아 그러네요. (A + B) % n = (A % n + B % n)%n 이게 맞습니다.

제 코드는 cnt = (cnt * 10) % n + 1%n; 이렇게 %n 이 하나 없는데, 왜 두 코드가 같은 건지 궁금한 겁니다.

>> (cnt * 10 % n + 1 % n) %n 이렇게 되어야 합니다. 이게 맞은 이유는 그러한 경우의 수가 나오지 않아서 그렇습니다.

예를 들어 (cnt * 10 % n + 1 % n) %n != (cnt * 10 % n + 1 % n)가 되려면 cnt * 10 % n + 1 % n = n 이상의 수가 나와야 하는데

cnt * 10 % n은 n 미만의 수를 가집니다. 최대 n - 1입니다.

1 % n은 1입니다. 즉, 합쳐서 최대 n이 되는데 이 때 n % n 은 0이 되며, %을 하지 않더라도 어차피 n이 더해지기 때문에 영향을 끼치지 않아서 그렇습니다.

저 근데 궁금해서 그러는데 제 코드의 어떠한 부분이 직관적이지 않다 생각하시나요?

감사합니다

네, 답변은 이해가 되었습니다. 결국, 강사님 코드가 동작한 이유는, 문제 요구사항이 마침 "1" 로 이루어진 수기 때문이네요.

만약 요구사항이 "3" 로 이루어진 수 였다면,

cnt * 10 % n + 3 % n 이 되고, 이건 n 보다 클 수 있기 때문에 틀렸을거 같습니다.

따라서 이 문제의 모범답안 코드는

#include<bits/stdc++.h>
using namespace std;  
typedef long long ll; 
int n;
int main(){ 
    while(scanf("%d", &n) != EOF){
        int cnt = 1, ret = 1; 
	while(true){
	    if(cnt % n == 0){
		printf("%d\n", ret);
		break;
	    }else{
		cnt = (cnt * 10)%n + 1; // 1 % n = 1  
		ret++;
	    }
	} 
}  
return 0;
} 

이게 좀 더 직관적일 것 같습니다. 결국

cnt = (cnt * 10) + 1; 
cnt %= n; 

이 코드는 모듈러 연산의 특성을 넘어서 추가적인 아이디어까지 접목해서 등장한 코드이면서 시간복잡도를 바꿀 정도로 효율적인 것도 아니기 때문입니다.