반응형
백준 4375번
레벨: 실버 3
언어: python
문제설명
2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.
이 설명을 듣고 이해가 잘 되지 않아서 찾아보았다.
예제 3이 출력에서 3으로 나오는 이유은 3의 배수 중에서 '111'이 1로만 이루어진 배수여서 '111'의 자리수가 3이기 때문에 출력이 3으로 나온다.
입력값
입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, n이 주어진다.
출력값
1로 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력한다.
📑풀이 과정
처음에는 브루트포스 문제여서 가장 단순하게 생각했다.
주어진 수에 직접 수를 곱하여 모든 자리가 1인지를 확인했는데 당연히 시간 초과가 나왔다.
그래서 모든 자리수가 1인 수를 만들고 주어진 수와 나머지연산을 하여 배수인지 확인했다.
이렇게 하니 푸는 시간이 확 줄어 들어서 시간 초과가 나오지 않았다.
밑 풀이 코드에 두 코드를 다 적어두겠다.
📋풀이 코드
정답 코드
import sys
arr = []
for i in range(10000):
num = sys.stdin.readline()
if num == '':
break
arr.append(int(num))
for num in arr:
cnt = 1
temp = 1
while(True):
if temp % num ==0: # temp가 num의 배수인지 확인
print(cnt)
break
cnt+=1
temp = temp*10 +1 # 10을 곱하고 1을 더해주어 모든 자리수가 1인 수 만들기
시간 초과 코드
입력은 위의 코드와 동일하다
배수의 길이 만큼 '1'을 곱하여 문자열을 만들고 문자열을 정수형으로 변환하여 같은 값인지 비교하였다.
for num in arr:
temp = 1
if temp % 2 ==0 or temp % 5 == 0: continue
while(True):
result = num * temp
number1 = '1'* len(str(result))
if result == int(number1):
print(len(str(result)))
break
temp +=1
반응형
'지난 글 모음' 카테고리의 다른 글
[백준 python] 2644번 촌수계산 DFS - 파이썬 (2) | 2022.02.25 |
---|---|
[백준 python] 1012번 유기농 배추 DFS/BFS (0) | 2022.02.23 |
[SW 정글] 4기 시험, 면접 후기 feat - 합격! (5) | 2022.02.13 |
[백준 node.js] 2805번 나무자르기 이진탐색 (0) | 2022.02.10 |
[백준 node.js] 1920번 수 찾기 (이진탐색) feat - 시간 초과, 메모리 초과 (0) | 2022.02.09 |