BOJ 1612, 가지고 노는 1
ProblemSolving ·이 문제는 수학 문제라고 생각합니다. (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;
}