[solved.ac 실버3] 4375_1 (python)

제한 사항

문제

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

입력

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

출력

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

 

---

나의 풀이

단순한 풀이

기본적인 아이디어로는 1, 11, 111, 1111... 순으로 늘려보며 n으로 나누어 떨어지는지 확인하는 방법을 생각해볼 수 있다.

틀린 풀이는 아니지만 큰 수를 나눠야 하는 상황이 발생하기 때문에 시간 복잡도가 증가할 수 있다.

PyPy3 언어로 백준에 제출한 결과 통과할 수 있었다.

해당 코드는 다음과 같다.

def solution(n):
    count = 1
    li = [0]
    while True:
        if int("1" * count) % n == 0: break
        count += 1
    print(count)

while True:
    try:
        solution(int(input()))
    except:
        break

테스트 결과

 

파이썬의 경우 정수 크기에 대한 제한이 없기 때문에 아주 큰 수를 직접 나눌 수 있지만 C, Java, C++ 등 대부분의 언어에서는 숫자가 커질 경우 int형이 아닌 long long int나 다른 타입으로 바꿔서 풀어야 하는 경우가 발생할 것이다.

이런 경우 Modula 연산을 사용하면 해결할 수 있다.

 

Modula 연산을 통한 풀이

Modula 연산은 나머지 연산이라고 할 수도 있다. 

입력으로 7이 주어진 경우를 생각해보자. 그리고 나눠질 수(1로만 이루어진 수)는 Dividend 라고 하겠다.

Dividend는 1부터 시작한다.

1. 1은 7로 나누어 떨어지지 않기 때문에 Dividend는 11로 커진다.
2. 11을 7로 나눈 나머지는 4가 남는다. 나누어 떨어지지 않았기 때문에 Dividend는 111로 커진다.
3. 111은 110 + 1 이다. (11 * 10) + 1 로 쓸 수 있다. 11을 7로 나눈 나머지가 4였기 때문에 (4 * 10) + 1 로 치환(11을 4로 치환)할 수 있고, (4 * 10) + 1 = 41을 7로 나눈 나머지는 6이 된다. 나누어 떨어지지 않았기 때문에 Dividend는 1111로 커진다.
4. 1111은 1110 + 1 이다. (111 * 10) + 1 로 쓸 수 있다. 111을 6으로 치환하면 61이 된다. 61을 7로 나눈 나머지는 5가 된다. 나누어 떨어지지 않았기 때문에 Dividend는 11111로 커진다.
5. 11111은 11110 + 1 이다. (1111 * 10) + 1 로 쓸 수 있다. 1111을 5로 치환하면 51이 된다. 51을 7로 나눈 나머지는 2가 된다. 나누어 떨어지지 않았기 때문에 Dividend는 111111로 커진다.
6. 111111은 111110 + 1 이다. (11111 * 10) + 1로 쓸 수 있다. 11111을 2로 치환하면 21이 된다. 21은 7로 나누어 떨어지기 때문에 Dividend인 111111은 7로 나누어 떨어진다고 할 수 있다.
7. 즉 정답은 6이 된다.

 

---

 

증명

어떻게 해서 위의 방법 중 치환이 가능한지 증명해보겠다.

입력된 숫자를 n이라고 하면 1로만 이루어진 Dividend는 nq + r 로 표현할 수 있다. 이때 r이 0이라면 나누어 떨어지는 경우이다.

1의 개수가 증가하면 위의 방법대로 ((nq + r) * 10) + 1로 표현할 수 있다. 이 식을 전개해보면 10nq + 10r + 1 로 표현할 수 있고, 이 식을 n으로 나눈 몫은 10q, 나머지는 10r + 1이 된다. 10r + 1이 0이라면 나누어 떨어지는 경우이다.

이 문제에서 나누어 떨어지는 경우만 생각하면 되기 때문에 나머지에 집중하면 된다. Dividend의 1이 하나 증가하면서  나머지는 r에서 10r+1로 커졌다.

즉, 이전 Dividend의 나머지 r에 10을 곱하고 1을 더한 것이 현재 Dividend의 나머지가 된다.

이 사실을 가지고 접근해보면 일종의 점화식이 완성된다.

 

개선된 풀이

def solution(n):
    count = 1
    li = [0]
    while True:
        dividend = li[count-1]*10 + 1
        if dividend % n == 0: break
        li.append(dividend % n)
        count += 1
    print(count)

while True:
    try:
        solution(int(input()))
    except:
        break

Modula 연산을 통해 코딩한 결과는 위 코드와 같다.

테스트 결과

첫 번째 풀이에 비해 실행 시간이 약 1.4배 빨라진 것을 확인할 수 있다.

 

---

입력 방법은 어떻게?

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

이 문제에서 입력을 보면 위와 같이 되어있다.

보통 무한히 입력을 받는 문제의 경우 0을 입력하면 입력받기를 종료한다거나 입력받을 데이터의 개수를 지정해주는 경우가 대부분인데 반해 이 문제는 테스트 케이스가 여러 개라고만 명시되어 있기 때문에 어떻게 입력을 받아야 할지 도저히 모르겠어서 다른 사람의 풀이에서 try ~ except 문을 사용한 것을 확인했다.

백준 사이트의 도움말 페이지를 다 뒤져봤지만 해당 내용은 발견할 수 없었다.

사실 이렇게 정답률이 낮을 문제가 아닌데 이런 문제가 원인이었을 가능성이 크다고 본다.

 

아까운 내 도전 횟수...ㅠ