BOJ 1612, 가지고 노는 1

수학

BOJ 1612, 가지고 노는 1

이 문제는 수학 문제라고 생각합니다. (BOJ4375 1이라는 문제에 상당히 유사합니다.)

풀이

저는 이 문제를 1, 11 , 111, 1111, … 숫자를 n으로 나눠보면서 나눠지면 그 자릿수를 출력했습니다.

하지만 이 문제의 핵심은 배수로 커져가는 숫자를 잘 처리하는 것이 핵심이죠!

이것은 1, 11, 111, 1111, … 이 숫자들을 그대로 가져다 쓰는 것이 아니라 n으로 나눈 나머지값들을 사용했습니다.

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

-> sum = (sum*10+1)%n 도 가능합니다. 이게 쉬울 것 같네요!

예를 들어 111을 n으로 나눈 나머지와 111, 두 수의 n으로 나눈 나머지값이 같다는 이러한 수학적 성질을 이용한 문제입니다.

뭔가 쉬운 것 같으면서 어려운 것 같고 그렇죠??

또 불가능하면 -1를 출력해야하는데 n이 2나 5로 나눠진다면 일의 자리수가 1이 될 수가 없어서 1로 만들어진 수를 만들 수가 없습니다!!

#include<stdio.h>
int n,sum, cnt;
int main()
{
	scanf("%d", &n);
	if (n % 2 == 0 || n % 5 == 0)
		printf("-1");
	else
	{
		do
		{
			sum = (sum % n) * (10 % n) + (1 % n);
			cnt++;
		} while (sum%n != 0);
		printf("%d\n", cnt);
	}
	return 0;
}

출처 : https://www.acmicpc.net/problem/1612