[BOJ/JAVA] 1612번: 가지고 노는 1

1612번: 가지고 노는 1

동물원에서 막 탈출한 원숭이 한 마리가 세상구경을 하고 있다. 이 원숭이는 수를 이리저리 가지고 노는 것을 매우 좋아한다. 그중에서도 1을 가지고 노는 것을 매우매우매우매우매우 좋아한다. 이제 원숭이가 1을 가지고 노는 법을 알아보자. 원숭이는 1만으로 이루어진 수를 매우매우매우매우매우매우매우 좋아한다. 그래서 어떤 자연수 N이 있을 때, N의 배수 중에서 1만으로 이루어진 수가 있을 까 생각하게 되었다.

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

키워드

• N의 배수 중에서 1만으로 이루어진 수중에 가장 작은 수의 자릿수

---

구현

countNumberLength

• 입력받은 값의 자릿수를 계산하는 메소드

1. 입력받은 정수를 String으로 바꾼다.

2. 해당 문자열의 길이를 반환한다.

solution

• 한자리 자연수 배수의 끝자리를 확인해보자

  1	2	3	5	7
  2	4	6	5	7
  3	6	9	10	14
  4	8	12	15	21
  5	10	15	20	28
  6	12	18	25	35
  7	14	21	30	42

• 2나 5의 경우 1의자리에 1이 나오지 않으므로, 2나 5로 떨어지면 -1을 반환한다.

• checkNumber
  • 자릿수를 하나씩 올리면서 증가시킨다.
  • checkNumber = checkNumber * 10 + 1

• 수가 너무 커지면 계산하기 어려우므로 줄여주는 작업이 필요하다.
  • 자릿수를 증가시킬 때 N으로 나눈 나머지값을 취한다.
  • 이 것이 왜 가능한지 살펴보자
  • 나머지 연산은 다음과 같다.

    $$a = q*d+r$$

  $$\begin{aligned} number&= a_1+a_2+...+a_n \\ number/N &= q*d+r \\ number/N &= (a_1/N+r_1)+(a_2/N+r_2)+...+(a_n/N+r_n) \\ number/N &= (a_1+a_2+...+a_n)/N + (r_1+r_2+...+r_n) \end{aligned}$$

  • 다음을 가정하자.

  $$r_a = a\%N \\ (a*10+1)\%N == ((a\%N)*10+1)\%N$$

  • 좌측항을 정리해보자.

  $$\begin{aligned} (a*10+1)\%N &= r \\ (a*10\%N)+1\%N &= r \\ (a\%N*10)+1\%N &= r \\ 10r_a+1\%N &= r \end{aligned}$$

  • 우측항을 정리해보자.

    나머지 연산의 분배법칙을 이용한다.

    

  $$\begin{aligned} ((a\%N)*10+1)\%N &= (r_a*10+1)\%N \\ (r_a*10+1)\%N &= r_a*10\%N + 1\%N \\ r_a*10\%N + 1\%N &= r_a\%N*10+1\%N \\ &= r_a*10+1\%N \\ &= 10r_a+1\%N \end{aligned}$$

  • 좌측항과 우측항이 같으므로, 나머지연산을 중간에 삽입해 크기를 줄일 수 있다.

---

코드

import java.util.Scanner;

public class java_1612 {
    static int N;

    // 입력받은 값의 자릿수를 계산하는 메소드
    static int countNumberLength(int number) {
        String stringNumber = Integer.toString(number);

        return stringNumber.length();
    }

    static int solution() {
        // 2나 5의 배수면 절대 만들 수 없음
        if (N % 2 == 0 || N % 5 == 0) {
            return -1;
        }

        int numberLength = countNumberLength(N);

        // 해당 값으로 나누어 떨어지는지 확인하기
        long checkNumber = 0;
        for (int i = 0; i < numberLength; i++) {
            checkNumber = checkNumber * 10 + 1;
        }

        int result = numberLength;
        while (true) {
            if (checkNumber % N == 0) {
                break;
            }

            checkNumber = (checkNumber % N) * 10 + 1;
            result++;
        }

        return result;
    }

    public static void main(String[] args) {
        // N의 배수중에서 1만으로 이루어진 수가 있는가?

        // N의 값보다 큰 1로만 이루어진 수가 N으로 나누어 떨어지는가?

        // 11 / 3 -> X
        // 111 / 3 -> O

        // 1 2 3 4 5 6 7 8 9
        // 2 4 6 8 10
        // 3 6 9 12
        //

        // 어떤 수가 N으로 나누어 떨어지는지 확인하는 방법?
        // N이 짝수인 경우 만들어지는가? -> X
        // N이 홀수인 경우부터 해보자.

        Scanner scanner = new Scanner(System.in);

        N = scanner.nextInt();

        int result = solution();

        System.out.println(result);

        scanner.close();
    }
}

---

Uploaded by N2T