백준 반복수[32687] 파이썬(Python) 코드 + 해설

백준 32687 반복수

백준 실버 3(Solved.ac) 문제번호 32687 반복수입니다.

 

1. 문제 소개

하나의 K자리 수를 원하는 만큼 연속해서 이어 붙인 뒤, 뒤에서부터 0개 이상의 연속된 숫자를 제거하여 만들어낸 K자리 이상의 수를 K-반복수라고 한다. A 이상 B 이하의 K-반복수 중에서 M으로 나누어떨어지는 수의 개수를 구하는 문제이다.

2. 문제 해결 방법

이 문제는 K가 최대 6이므로 가능한 K자리 수를 모두 탐색해도 시간 내에 해결할 수 있다.

해결 전략은 다음과 같다:

1. K자리 수 생성:
   • K자리의 수 S는 10^{K-1}부터 10^{K}-1까지다.
   • 이러한 S에 대해 무한히 반복된 문자열을 생성한다.
2. 반복된 문자열에서 가능한 길이의 접두어 생성:
   • 각 S에 대해 무한히 반복된 문자열 infinite_S를 생성한다.
   • 길이 L을 K부터 B의 자리수까지 반복한다.
   • infinite_S의 앞에서부터 길이 L의 접두어를 추출한다.
3. 조건 검사 및 개수 세기:
   • 생성된 수가 A 이상 B 이하인지 확인한다.
   • 생성된 수가 M으로 나누어떨어지는지 확인한다.
   • 조건을 만족하면 개수를 증가시킨다.

구현 시 주의사항:

• 무한히 반복된 문자열의 길이 조절:
  • 필요한 만큼만 반복하여 문자열을 생성한다.
  • 길이 L이 증가함에 따라 infinite_S를 동적으로 확장한다.
• 중복 제거:
  • 동일한 숫자를 중복해서 세지 않도록 주의해야한다.

 

3. 백준 32687 반복수 파이썬(Python) 정답 코드

import sys
input = sys.stdin.readline

A_str, B_str, K_str, M_str = input().split()
A = int(A_str)
B = int(B_str)
K = int(K_str)
M = int(M_str)

count = 0

start_S = 10 ** (K - 1)
end_S = 10 ** K

max_len = len(B_str)

for S in range(start_S, end_S):
    str_S = str(S)
    infinite_S = str_S
    L = K
    while True:
        # 필요한 만큼 infinite_S를 확장
        while L > len(infinite_S):
            infinite_S += str_S
        N_str = infinite_S[:L]
        N_int = int(N_str)
        if N_int > B:
            break
        if N_int >= A and N_int % M == 0:
            count += 1
        L += 1
        if L > max_len:
            break

print(count)

4. 백준 32687 정답 코드 추가 설명

• 시간 복잡도:
  • K는 최대 6이므로, K자리 수는 최대 9×10^{K-1}개다.
  • 각 S에 대해 길이 L은 최대 12까지 증가하므로, 전체 반복 횟수는 약 900,000×9로 약 8,100,000번의 연산으로 제한 시간 내에 해결할 수 있다.
• 중복 제거:
  • 각 S에 대해 길이 L를 증가시키며 접두어를 생성하므로, 중복된 숫자를 생성하지 않는다.
• 정확성:
  • 문제에서 요구하는 K-반복수의 정의에 따라 정확하게 모든 가능한 수를 생성하고 조건을 검사한다.

 

5. 백준 32687 제출 결과

백준 32687 반복수

 

도움이 되셨다면 공감과 댓글 부탁드립니다