[백준 01612] 가지고 노는 1 [Java]

문제

https://boj.ma/1612

1612번: 가지고 노는 1

 

---

풀이

문제 요약

주어진 N의 배수 중 1로만 이루어진 자연수의 길이를 출력하자. 만약 없다면 -1을 출력하자.

아이디어

N이 2 또는 5로 나누어 떨어진다면, 1로만 이루어진 자연수(=N*K)는 존재하지 않는다.

따라서 N으로 나누어 떨어지는 NK를 찾으면 된다. NK가 너무 커질 수 있으니, N으로 나눈 나머지를 이용하자.

    private static int solve(int N) {
        if (N % 2 == 0 || N % 5 == 0) {
            return -1;
        }
        int likeNum = 0;
        int cnt = 0;
        do {
            likeNum = (10 * likeNum + 1) % N;
            ++cnt;
        } while (likeNum % N > 0);
        return cnt;
    }

풀이 시간

30분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/normal/01612.java

problem-solving/baekjoon-online-judge/normal/01612.java at main · rogi-rogi/problem-solving