[백준] 1951 활자 with Python

📌 BOJ 1951 활자

💡 조건

1. N(1 ≤ N ≤ 2,000,000,000)

2. 가나다라는 글씨를 쓰기 위해서는 3개의 활자가 필요하다.
   N이하의 자연수를 활자로 표현하기 위해서는 몇 개의 활자가 필요한지 구하는 문제

3. 10이하의 자연수를 활자로 표현하려면 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0 이렇게 11개의 활자가 필요하다.

4. 첫째 줄에 필요한 활자의 수를 1234567로 나눈 나머지를 출력.

5. 수학 유형의 문제

🖥 소스 코드

n = int(input())
s = [0 for i in range(10)]
point = 1
while n != 0:
    while n % 10 != 9:
        for i in str(n):
            s[int(i)] += point
        n -= 1
    if n < 10:
        for i in range(n + 1):
            s[i] += point
        s[0] -= point
        break
    else:
        for i in range(10):
            s[i] += (n // 10 + 1) * point
    s[0] -= point
    point *= 10
    n //= 10

print(sum(s) % 1234567)

🔖 예제 및 실행결과

예제

10

실행결과

11

⌨️ 문제 풀이

1. 일단 먼저, N의 크기를 확인해보자. N이 무려 2억을 넘어 천장을 뚫고 20억이다.
   1부터 N까지 올라가면서 각 숫자를 세어본다는 아이디어에서 못벗어나 코드를 짰다면 반성해야하며, 난 반성하고 있다.

2. 0부터 9까지 몇 개의 숫자를 사용했는지 저장할 리스트 s를 만든다.

3. N이 0 이 될 때까지 반복문을 돌려주면되는데,

   1. N 을 10으로 나눈 나머지가 9가 아닐 경우, n을 문자열로 만들어 s[해당 숫자]에 point 만큼 숫자를 더해준다.
      그 후 n - 1 을 해준다. 이 작업은 10으로 나눈 나머지가 9가 될 때까지 반복한다.
      이 후, 아래의 두가지 조건을 다시 살펴본다.

   2. N 을 10으로 나눈 나머지가 9이며 10보다 작을 경우, 각 자리의 값을 point 만큼 늘려준다 0에 해당하는 숫자는 point를 빼준다.
      이 작업이 완료되면 break.

   3. N 을 10으로 나눈 나머지가 9이며 10보다 클 경우, s를 순회하면서 s[i]의 값을 (n // 10 + 1) * point 만큼 늘려준다.

   이 세가지 조건문에 해당하는 작업을 완료하고, s[0] - point, point의 값을 * 10, n // 10 을 해준다.

4. (3-1) 조건은 1의 자리 수를 9가 아닌 수로 만들기 위해서 하는 작업이다.
   9는 0~9까지 한번씩 모두 사용하기 때문이다.

5. (3-2) 조건은 N이 한자리 수로 떨어졌을 때, 사용할 조건이다. 굳이 뭘 계산할 필요없이 s의 각 원소에 point를 더해주면 된다.