[Backjoon_4375] 1 (Java)

문제 링크

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

4375번: 1

문제 요약

<문제>

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

 

<입력>

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

 

<출력>

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

 

<제한사항>

시간 제한 1초

메모리 제한 128MB

 

문제 풀이

n을 입력받아 n의 배수중 1로만 이루어진 가장 작은수를 찾는 문제이다.

n의 배수 == n으로 나누면 0  이므로 1로 수를 만들어 n으로 mod  연산을 하여 0이 되는 값을 찾는 방법으로 해결할 수 있다.

1을 추가하여 계산을 할 경우 integer max범위를 넘어갈 수 있으므로 나머지 연산의 특징을 활용하여 해결하여야 한다.

 

우선 1을 추가할 때의 규칙을 파악하였다.

a1 = 1 

a2 = 11 (a2 = a1*10 + 1)

a3 = 111 (a3 = a2*10 + 1)

a4 = 1111 (a4 = a3*10 + 1)

이므로 전 값에서 10을 곱하고 1을 더하면 되는것을 알 수 있다.

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

%연산은 *와 + 에서 분배법칙이 성립하므로 이전에 구한 값에 10을 곱하고 1을 더한 후 %연산을 하여도 똑같다.

for문으로 현재 1의 개수를 표현하여주고, 주어진 num으로 %연산을 하고 만약 나누어 떨어지면 출력하는 방법으로 해결하였다.

 

구현 코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while(sc.hasNextInt()){
            int num = sc.nextInt();
            int prev = 0;
            for(int i = 1;;i++){
                prev = (prev*10+1)%num;
                if(prev == 0) {
                    System.out.println(i);
                    break;
                }
            }
        }
    }
}

 

시간복잡도

Test Case 문제로 테스트케이스의 수 * 나머지 연산 이다.

O(T*C) ( T : 테스트케이스 수 , C : 나머지 연산해서 찾는 수)