백준 - 1(JAVA)

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처 : https://www.acmicpc.net/problem/4375

[문제 설명]

1,11,111,1111,11111

주어진 숫자를 배수해서 만들 수 있는 1로 이루어진 숫자는 몇번째 숫자인지 구하시오.

예: 

입력이 3일 때 3에 37을 곱한 111이 1로 이루어진 숫자다. 즉, 1로 이루어진 세번째 숫자.

입력이 7일 때 111111은 7의 배수다. 즉, 7로 이루어진 6번째 숫자.

 

[접근 방법]

문제를 딱 봤을 때, 엄청 쉽네 생각하고 풀었다가 오버플로우나 시간 초과나서 망하기 좋은 문제.

백퍼센트 각각의 값에 관계가 있다.

일단 우리에게 주어진 숫자가 n이라고 보자.

그렇다면 아래와 같은 식이 무조건 성립한다.

 

1 = n*몫+나머지

11 = 1*10+1 = 10(n*몫+나머지)+1 = 10*n*몫 + 10*나머지+1

=> 10*나머지+1이 몫보다 크면 (10*나머지+1)/n이 몫으로 가고 (10*나머지+1)%n이 나머지로 간다.

예를 들어보자. n이 3으로 주어졌을 때.

1 = 3*0+1

11 = 10(3*0+1)+1 = 10*3*0+10+1 => 11/3은 몫, 11%3은 나머지

111 = 10(3*3+2)+1 .......

 

즉, An이 n번째 나머지라 하고, 주어진 숫자가 X라고 할 때.

An+1 = (An*10+1)%X이 성립한다.

X=3이면

A2 = (A1*10+1)%3 = (1*10+1)%3 = 2

A3 = (A2*10+1)%3 = (2*10+1)%3 = 0

 

[코드]

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = null;
        while ((str = br.readLine()) != null) {
            // an
            int indexOfNumber = 1;
            int N = Integer.parseInt(str);
            int rest = 1%N;

            while (rest != 0) {
                indexOfNumber++;
                rest = ((rest)*10+1)%N;
            }

            System.out.println(indexOfNumber);
        }
    }
}

생각보다 빨라서 기분 좋았다.