백준 4375/c++ )) 1 모듈러 연산에 대한 이해

1 , 11, 111, 1111, 11111  식으로 늘어나는 수 중에 입력한 a의 수의 배수인(a으로 나눠서 나머지가 0인) 

최소값의 자리수를 구하는 문제이다

c++의 경우 표현할 수 있는 숫자의 크기가 정해져있으므로 자리수도 무한정 늘릴 수 없다

자리수가 올라갈때마다 자리수 nu에 ++ 해주고, 규칙에 의해 자리수가 올라가고 새로 취한 수는

 모듈러 연산을 이용하여 나머지 값만 취하고 a의 배수인지 확인, 나머지가 0이면 배수이므로 그때의 자리수를 출력,

그렇지 않으면 다시 일정한 규칙으로 수를 기존 나머지값에 적용하여 반복하여 구하는 문제이다

입력의 경우 끝나지 않고 계속 받으므로, "cin.eof() 입력의 끝" 이 "아니다  ! " 가 참일 동안 while 을 통해

입력을 계속 유지하였다  while(@cin.eof())   이 함수도 꼭 외워두자

 

설명이 장황한만큼 코드 주석도 길다

그만큼 이해하기까지도 오래걸린 문제이다... 모듈러 연산... 반복문 내에서 재귀처럼 한 변수를 계속 사용하는데

이럴때 매우 까다롭다 꼭 다시 보고 풀어보자

#include <bits/stdc++.h>
using namespace std;

void solution(int a){
		
	int tok=1;
	int nu=1;
	
	while(true){
		if(tok%a==0){
			cout << nu << "\n";
			break;
		} else {
		// 이전 sum 을 사용해서 다음 sum을 구한다 			tok=tok*10+1;			// 모듈로 연산 시, tok을 a로 나눌때 tok=x+y이다 
		// x는 tok 이하중 a의 최대 배수부분이고  y는 x를 뺀 나머지이다
		// tok%는 즉, (x+y)%a 와 같고 모듈러 연산 공식에 의해  
		// 이는 ((x%a) + (y%a)) %a  의 값과 같다. y는 이미 나머지이므로 y%a 는 y와 같다 
		// x는 a의 배수이므로 나누어 떨어져서 x%a =0 이 되고
		// 나머지인 y 만 남아 다시 y%a 를 해도 y 가 된다
		// 즉, tok%a 의 결과는 tok의 나머지부분인 y 와 같다
		// 이 나머지 값을 다시 tok 에 할당한다. 과연 추후 연산에 영향을 줄까?
		// 문제없이 작동하는데 그 이유는 다음과 같다 
		// tok = y 인데 그 값이 0 이면 반복을 멈추고 그때의 자리수를 반환하여 끝나지만  
		// tok 의 값인 y가 0이 아니라면 앞자리에 1을 추가하여 반복한다
		// 이때 tok은 이전 tok 의 나머지 값을 가졌으므로  
		// tok = y*10+1 이 된다. 이 수도 a로 나눠지는지 확인해야 하므로 모듈로 연산하면  
		// tok = (y*10+1)%a 가 되고 이는 ((y%a)*(10%a)+1%a)%a가 된다  
		// 문제에서 a는 2와 5의 배수가 아니라 했으니 10은 나눠지지 않는 수이므로 
		// 나머지 y를 tok으로 할당하여 계산한 다음 수의 나머지 값은 tok = (y*10+1)%a 가 된다
		// 하지만 아까 나머지가 아닌 수를 그대로 tok 에 전달해서 다시 반복했었으면 답이 어땠을지 비교해보자
		// tok = ((x+y)%a*10+1) 가 되고 이는 (((x%a)+(y%a))%a*10+1)%a 이고 x%a==0이므로
		// 나머지가 아닌 그대로 전달해도 다음 수의 나머지값 tok = (y*10+1)%a 가 된다
		
		// 결국 나머지를 전달하던 나머지를 구하기 전 수로 전달하던 그수를 이용한 다음 모듈로 연산은 같다는 것이다
		// 오버플로우를 막기위해서라도 모듈로 계산 후 나머지로 전달하도록 하는 것이 이문제의 핵심이다
		
		// 이 문제를 통해서 이후 모듈로 연산 할 시,
		// 이전 값을 모듈로 연산하여 보내도 후의 모듈로 값에 영향이 없다는 점을 깨달았다  
		tok = (tok*10) + 1;
		tok = tok%a;
		nu++;
		}
	}	
}

int main(){
	
	int g;
	
	while(cin >> g){
		solution(g);
	}
	
	return 0;
}