백준 알고리즘 | 4375번 문제: 1

Tags:

출처

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

문제

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.

출력

1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.

예제 입력 1

3 7 9901

예제 출력 1

3 6 12

알고리즘 분류

  • 수학
  • 브루트포스 알고리즘
  • 정수론

문제 풀이

1로만 이루어진 수란? 1, 11, 111 와 같은 수를 말한다.
배수란? 어떤 1배, 2배, 3배… 한 수를 그의 배수라고 한다. 3, 6, 9…은 3의 배수 이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {

            String str = null;
            while ((str = br.readLine()) != null) {
                final int n = Integer.parseInt(str);

                int x =1;
                for (int i = 1; ; i++) {
                    x = x % n;
                    x = x * 10 + 1;
                    if (x == 1) {
                        System.out.println(i);
                        break;
                    }
                }
            }
        }
    }
}

위 코드에서 값은 변화는 아래와 같다.

      1 % 7 = 1                                                | n = 7, x = 1  > 11, i = 1 
     11 % 7 =      (1 % 7) x 10 + 1 = 10 + 1 = 11 , 11 % 7 = 4 | n = 7, x = 11 > 41, i = 2 
    111 % 7 =     (11 % 7) x 10 + 1 = 40 + 1 = 41 , 41 % 7 = 6 | n = 7, x = 41 > 61, i = 3
   1111 % 7 =    (111 % 7) x 10 + 1 = 60 + 1 = 61 , 61 % 7 = 5 | n = 7, x = 61 > 51, i = 4
  11111 % 7 =   (1111 % 7) x 10 + 1 = 50 + 1 = 51 , 51 % 7 = 2 | n = 7, x = 51 > 21, i = 5
 111111 % 7 =  (11111 % 7) x 10 + 1 = 20 + 1 = 21 , 21 % 7 = 0 | n = 7, x = 21 >  1, i = 6
1111111 % 7 = (111111 % 7) x 10 + 1 =  0 + 1 =  1              | n = 7, x = 1  >  1

참조 문서

알고리즘 | 나머지연산(Modular Arithmetic : mod)




최종 수정 : 2022-06-12