[백준/파이썬][Silver III] Champernowne Count - 27569

[Silver III] Champernowne Count - 27569

문제 링크

성능 요약

메모리: 109544 KB, 시간: 100 ms

분류

수학, 정수론

제출 일자

2025년 2월 7일 02:22:19

문제 설명

The $n$th Champernowne word is obtained by writing down the first $n$ positive integers and concatenating them together. For example, the $10$th Champernowne word is "12345678910".

Given two positive integers $n$ and $k$, count how many of the first $n$ Champernowne words are divisible by $k$.

입력

The single line of input contains two integers, $n$ $(1 \leq n \leq 10^{5})$ and $k$ $(1 \le k \le 10^{9})$.

출력

Output a single integer, which is a count of the first $n$ Champernowne words divisible by $k$.

풀이

def main() :
    n, k = map(int, input().split())
    num = cnt = 0

    for i in range(1, n + 1) :
        mul = pow(10, len(str(i)), k)
        num = (num * mul + i) % k
        if num % k == 0 :
            cnt += 1
    print(cnt)

main()

1. 입력 및 초기화

n, k = map(int, input().split())
num = cnt = 0

• 입력 받기 : 사용자로부터 두 개의 정수 $n$과 $k$를 입력받습니다.
  
  • $n$ : 1번째부터 $n$번째까지의 챔퍼나우언 단어를 고려
  • $k$ : 각 챔퍼나우언 단어가 $k$로 나누어 떨어지는지(즉, 나머지가 0인지) 확인하는 기준
• 변수 초기화 :
  • num : 현재까지 만들어진 챔퍼나우언 단어의 정수 값(모듈러 $k$로 축소한 값)을 저장
  • cnt : $k$로 나누어 떨어지는 챔퍼나우언 단어의 개수를 카운트

2. 각 단계별로 챔퍼나우언 단어 갱신하기

for i in range(1, n + 1) :
    mul = pow(10, len(str(i)), k)
    num = (num * mul + i) % k
    if num % k == 0 :
        cnt += 1

• 반복문 설명 : i가 1부터 $n$까지 증가하면서, 각 $i$를 현재까지의 단어에 "이어 붙이는" 과정을 수행
• mul = pow(10, len(str(i)), k) 부분 :
  • len(str(i)) 는 $i$의 자릿수를 구합니다.
    예를 들어, $i = 123$이면 자릿수는 3입니다.
  • pow(10, len(str(i)), k) 는 $10^{자릿수}$ 를 $k$ 로 나눈 나머지를 계산합니다.
    이 연산은 모듈러 거듭제곱을 사용하여 효율적으로 계산합니다.
  • 이 값은 현재까지의 수 num에 $i$를 이어 붙이기 전에 자릿수를 올려주는 역할을 합니다.
    • 예를 들어, 현재 num 이 "123" (정수 123)이고, $i$가 45 (자릿수 2) 라면, 
      새로운 단어는 "12345"가 되어야 하므로 $10^{2} = 100$ 을 곱한 후 $i$를 더합니다.
  • 단, 이 때 매번 큰 수를 다루지 않기 위해서 모듈러 $k$를 적용하여 mul 값을 구합니다.
• num = (num * mul + i) % k 부분 :
  • num * mul 은 기존의 챔퍼나우언 단어를 자릿수만큼 왼쪽으로 옮깁니다.
  • 여기에 현재의 $i$를 더해줌으로써, 새로운 챔퍼나우언 단어를 구성합니다.
  • 마지막에 % $k$ 를 하여, 그 결과를 $k$로 나눈 나머지만 남깁니다.
  • 이렇게 하면 실제로 매우 큰 정수를 다루지 않고도, 결과적으로 k에 대한 나머지를 유지할 수 있습니다.
• if num % k == 0 : 부분 :
  • 매번 업데이트된 num 이 0인지 (즉, $k$로 나누어 떨어지는지) 확인합니다.
  • 만약 나누어 떨어진다면 cnt 를 1 증가시킵니다. 

코드의 핵심 아이디어 요약

• 모듈러 연산 활용 : 
  실제로 무낮열을 생성하거나, 매우 큰 수를 직접 계산하지 않고도, 모듈러 연산을 통해 $k$에 대한 나머지 값만을 추적합니다.
• pow 함수 사용 : 
  pow(10, len(str(i)), k) 를 사용하여 $10 ^ {자릿수}$를 효율적으로 $k$ 모듈러 연산과 함께 계산합니다.
• 효율적 계산 : 
  이 방식 덕분에 $n$이 커져도 각 단계에서 다루는 수가 $0$부터 $k - 1$ 사이의 값으로 제한되어, 시간 및 메모리 측면에서 매우 효율적으로 문제를 해결할 수 있습니다.

def main() :
    n, k = map(int, input().split())
    num = cnt = 0
    for i in range(1, n + 1) :
        num = (num * (10 ** len(str(i))) + i) % k
        if num % k == 0 :
            cnt += 1
    print(cnt)
main()

첫 번째 코드와 두 번째 코드는 num을 계산하는 부분이 pow(10, d, k) 의 형태로 자주 해주는 것이 아니라, 새롭게 갱신된 num 에 대해서 % k 를 해주는 것이라 조금 비효율적으로 작동할 수 있다. 

두 번째 코드의 특징 및 한계

• 직접 거듭제곱 계산 : 
  
  • 이 코드에서는 10 ** len(str(i)) 를 사용하여 거듭제곱을 직접 계산합니다.
  • 이 경우, 매 반복마다 거듭제곱 연산이 수행되는데, 파이썬에서는 거듭제곱 연산이 내장되어 있으므로 기능적으로는 문제가 없지만, 
    모듈러 연산을 바로 적용하는 첫번째 코드에 비해 효율성 면에서 다소 떨어질 수 있습니다.
• 성능상의 차이 :
  • $n$의 범위가 클 경우, (예: $n = 10^{5}$) 특히 $k$ 가 큰 값이라면, 직접 거듭제곱을 계산하는 연산이 부담될 수 있습니다.
  • 결과적으로 두 번째 코드는 첫 번째 코드보다 시간 효율성이 떨어질 수 있습니다.
• 모듈러 연산 : 
  • 결과적으로 두 번째 코드도 매 단계에서 모듈러 연산을 수행하여, num의 값을 $k$ 범위 내로 유지하는 점은 동일합니다.
  • 그러나, 매번 $10^{자릿수}$를 직접 계산한 후 모듈러 연산을 적용하는 방식은 특히 큰 $k$ 값이나 많은 반복 횟수에서 성능에 영향을 줄 수 있습니다.

요약

두 번째 코드는 기본적으로 챔퍼나우언 단어를 모듈러 연산을 사용해 구성하는 방식은 동일합니다.
그러나,

• 첫 번째 코드는 pow(10, len(str(i)), k)를 사용하여 거듭제곱과 모듈러 연산을 동시에 처리해 효율성을 높였고,
• 두 번째 코드는 10 ** len(str(i))로 직접 계산한 후 모듈러 연산을 적용합니다.

따라서, 두 번째 코드는 기능적으로는 올바르지만,
큰 입력에 대해 성능 최적화 측면에서는 첫 번째 코드에 비해 덜 효율적일 수 있다는 점을 이해해야 합니다.