백준_4375 : 1 - 모듈러 산술

n을 입력하면 1, 11, 111, 1111... 쭉 늘려가면서 n으로 나눌 시 나머지가 0인 걸 찾는 문제다.

그때의 1의 개수가 몇인지. 가장 작은 거 출력.

 

처음엔 간단하다! 이러고 우다다 작성.

일단 n이 뭐 4자리 수면 n의 배수니까 4자리 수보단 클 테니까 자릿수 구하는 함수 만들어서 조금이나마 반복횟수를 줄이려고 했는데 생각해보면 굳이.. 자릿수 함수를 만든다고 반복횟수가 크게 달라지나 싶다.

 

<오답>

#include <stdio.h>

long long J1111; // 걍 J1은 임팩트가 없어서 1111로 적음.
int getJaritso(int n);

int main() {
	int n;
	int J;
	while (scanf_s("%d", &n) != EOF) {
		J1111 = 1;
		J = getJaritso(n);

		J1111 = J1111 * 10 + 1; // 생각해보니 입력한 수보단 어쨌든 자릿수가 크니까.
		while (J1111 % n != 0) {
			J1111 = J1111 * 10 + 1;
			J++;
		}
		J++;
		printf("%d\n", J);
	}
}


int getJaritso(int n) { // J랑 J1111 값 구하는 함수
	int J = 1;
	while (n / 10 != 0) { // n이 한자리수가 될 때까지
		n /= 10;
		J += 1; // J는 자릿수
		J1111 = J1111 * 10 + 1; // 자릿수만큼 1 (ex. J가 3이면 J10은 111)
	}
	return J;
}

 

그냥 생각난대로 짰음. 1, 11, 111...로 늘려가면서 나머지가 0일 때까지 반복하기.

 

처음엔 출력이 이상해서 J1111의 범위를 long long으로 바꾸었더니 잘 나왔다.

 

근데 이러니까 제출했더니 시간초과가 떴다.

그래서 검색을 했더니 모듈러 산술을 사용해서 푸는 문제라는 거다.

 

참고한 블로그

- https://ko.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic

-  https://velog.io/@dianestar/%EB%B0%B1%EC%A4%80BOJ-4375%EB%B2%88-1

 

<정답>

#include <stdio.h>

int main() {
	int n;
	// 모듈러 연산으로 풀어야 하는 문제.
	while (scanf_s("%d", &n) != EOF) {
		int M = 1;
		int k = 1;
		while (M % n != 0) {
			M = (10 * M + 1) % n;
			k++;
		}
		printf("%d\n", k);
	}

	return 0;
}

 

너무 간단해서 어이가 없다.