[BOJ] 4375. 1

Jimeaning·2024년 2월 28일

브루트포스 수학 정수론

코딩테스트

목록 보기

142/143

Python3

문제

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

키워드

수학
브루트포스 알고리즘
정수론

문제 풀이

문제 요구사항

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 각 자릿수가 모두 1로만 이루어진 n의 배수를 찾는 프로그램

각 자릿수가 모두 1로만 이루어진 n의 배수 중 가장 작은 수의 자리수를 출력

변수 및 함수 설명

n : 입력받는 정수
one : 각 자릿수가 모두 1로만 이루어져 있는 문자열
cnt : one의 1 개수

풀이

문제의 종료 조건 정하기
종료 조건이 따로 없어 try, except문을 사용해서 풀어야 했다.
문제 접근법
처음에 문제가 이해가 안 돼서 접근 방법만 큰돌 강의를 참고했다.
1로만 구성되어 있는 수가 있고(1, 11, 111, 1111..) 입력받은 n을 1로만 이루어진 수로 나누었을 때, 나누어 떨어지면 해당 숫자의 1 개수를 출력하는 문제이다.
예를 들면, n이 3일 때 111이 3으로 나누어 떨어진다.
이렇게 ..
나누어 떨어지는 수(배수) 중 가장 작은 값을 출력하라 했으므로 n이 3일 때는 3이 출력되는 것이다.
-> 즉 1로만 이루어진 수와 n이 나누어 떨어지면 해당 수의 1 개수를 출력하고, 그렇지 않으면 계속 1을 붙여 가면서 반복문을 돈다.
one과 cnt 사용 이유
변수를 '배수' 하나만 두고 풀 수도 있겠지만 1의 개수를 확인하는 과정에서 또 반복문을 쓰게 될 것 같아서 cnt 변수를 하나 더 두었다.
one은 string으로 지정해 1, 11, 111, 1111..이 되도록 하고, 1이 늘어날 때마다 cnt값도 1씩 증가해 1의 개수를 동시에 카운트했다.

최종 코드

while True:
    try:
        n = int(input())
    except:
        break
        
    one = '1'
    cnt = 1
    
    while True:
        if int(one) % n == 0:
            print(cnt)
            break
    
        one += '1'
        cnt += 1