[Python] 백준 4375번: 1 (나머지, 부르트포스, 파이썬)

문제 출처:

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

4375번: 1

 

※ BruteForce Algorithm(부르트포스)

 

문자 그대로 Brute Force(야성적인 힘), 완전탐색 알고리즘이라고 불린다. 발생할수 있는 모든 케이스들을 무식하게 대입해가며 답을 찾는 방식 이다. 단순하고 설계가 쉽다는 장점이 있지만, 그만큼 속도와 메모리 측면에서 비효율적이라는 단점을 가지고 있다.

 

문제

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

 

입력

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

 

출력

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

풀이 방법

우선 문제의 이해부터가 약간 애매하다. 예시가 직관적으로 주어지지 않아 정확히 뭘 구하라는 건지가 헷갈리기 때문인데, 간단히 설명하면 다음과 같다. 입력된 n의 배수 중 1,11,111,1111,1111,11111.... 이렇게 1로만 이루어진 숫자가되는 최소 값을 찾은뒤, 그 자리 수를 구하는 것이다. 

예를 들면, 3의 배수 중 1로만 이루어진 최소정수는 111. 물론 111111,111111111도 3의 배수 중 1로만 이루어진 수 이지만 문제에서 원한것은 최소배수의 자리 수를 물었기에 출력은 3 이다.

 

문제를 이해했다면 풀이방법은 크게 두 파트로 나뉜다. 1)여러개의 입력을 계속 받아오는 파트, 2)1로만 이루어진 숫자를 생성하는 파트. 

 

1번 파트 부터 살펴보자. 한 번에 하나의 값만 입력된다는 부분을 보면 단순히 input() 를 사용하여 int 자료형으로 변환만 해주면 되는것 같아 보인다. 그러나 여기서 입력값이 당연히 정수형만 있을것이라고 생각하고 코드를 작성하면 오답이 발생한다. EOF(End of File)을 고려해주기 않았기 때문이다(EOF에 대한 내용은 본 블로그 python 카테고리에 따로 정리해두었다).

 

2번 파트는 여러 풀이법이 존재한다. mod연산자로 정수론을 활용하는 풀이법도 있지만 난 가장 간단한 방법들 몇개를 작성해보았다.

• pow(10,n)을 이용하여 10의 n승을 계속 더 해주는 방법
• pow(10,n)을 이용하여 10의 n승을 만든 후 1을 빼주어 9로만 이루어진 정수를 만든뒤 9로 나누어 구하는 방법
• str 자료형으로 '1'로만 이루어진 배열을 만든 후 int 자료형으로 변환하는 방법

단순무식하게 자릿수를 하나하나 올려가며 답을 찾는 대표적인 BruteForce 알고리즘을 사용하는 문제이다. 다만 3번 풀이의 경우 C++ 이나 C에서는 오히려 코드 복잡도만 올라가니 자료형의 변환이 자유로운 Python에서 시도해볼만한 방법일 것 같다.

while True:
    try:
        x = int(input())
    except:
        break

    if x == 1:
        print(x)
    else:
        """
        1. 10의 n승을 더해가는 방법
        """
        n = 1
        while 1:
            onenum = 1
            onenum = pow(10,n) + onenum
            n += 1
            if int(onenum%x) == 0:
                print(n)
                break
        """
        2. 10의 n승에서 1을 뺀후 9로 나눈 몫으로 구하는 방법
        """
        n = 1
        while 1:
            onenum = (pow(10,n+1)-1)//9
            n = n+1
            if int(onenum%x) == 0:
                print(n)
                break
        """
        3. 1로 이루어진 str을 만든후 int로 변환하는 방법
        """
        onenum = '1'
        while 1:
            onenum = onenum + '1'
            if int(int(onenum)%x) == 0:
                print(len(onenum))
                break