[백준] 1081 합 with Python

📌 BOJ 1081 합

💡 조건

1. L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 문제.
   0 ≤ L ≤ U ≤ 2,000,000,000

2. 수학 유형의 문제

🔖 예제 및 실행결과

예제

24660 308357171

실행결과

11379854844

⌨️ 문제 풀이

1. 가장 먼저 문제를 보며 주목해야할 부분은 L과 U의 범위이다.
   L과 U의 범위는 최대 20억까지로, 일일히 검사했을 때 최악의 경우에는 0부터 20억까지의 모든 수를 검사해야하기 때문에
   문제에서 주어진 2초라는 시간 안에 절대 해결할 수가 없다.

2. (1)번에서 정리한대로, 우리는 L과 U의 범위를 입력받아 일일히 숫자 하나씩 검사하는 방법을 피해 각 숫자의 자릿수를 더해 답을 출력해야 한다.
   L, U 를 입력받아 L보다 크거나 같고, U보다 작거나 같은 모든 정수의 각 자리의 합을 구하는 것은 어느 일정 구간에 대한 합을 구하는 것과 같다.
   구간합의 개념으로 생각을 해보자.

3. L - 1 까지 등장한 0~9의 개수를 K, U까지 등장한 0-9 의 개수를 P 라고 했을 때,
   (P - K) 는 L 부터 U 의 범위에 해당하는 0-9의 개수라는 것을 의미한다.

4. L = 1000, U = 1234 라고 가정했을 때, 접근 방법은 두가지가 있다.
   • 1의 자리에서부터 0~9까지의 등장 횟수를 count 할 것인가?
   • 가장 높은 자리에서부터 0-9까지의 등장 횟수를 count 할 것인가?
     일단 본인의 풀이는 1의 자리에서부터 0~9까지의 숫자를 count 했다.

5. 먼저, 1의 자리에 어떤 숫자가 몇 번 등장하는지에 대해서 살펴보자. 먼저 0부터 살펴보자.
   10 ~ 90 : 10
   100 ~ 190, 200 ~ 290, ... ,900~990 : 90
   1000 ~ 1090, 1100 ~ 1190 : 20
   1200 ~ 1230 : 4
   총 124 회

6. 1의 자리에서 5가 몇번 등장할까?
   15 ~ 95 : 10
   105 ~ 195, 205 ~ 295, ... ,905 ~ 995 : 90
   1005 ~ 1095, 1105 ~ 1195 : 20
   1205 ~ 1225 : 3
   총 123 회

7. 10의 자리에서 4는 몇 번 등장할까?
   40 ~ 49 : 10
   140 ~ 149, 240 ~ 249, ..., 940 ~ 949 : 90
   1040 ~ 1049, 1140 ~ 1149 : 20
   총 120 회.

8. 여기서 알 수 있는 것은, 우리는 이렇게 숫자의 자릿수 별로 각 숫자가 몇번씩 등장하는지 계산할 수 있다는 것이다.
   또한, 10의 자리에서 4가 몇 번 등장하는지를 셀 때에는 1234를 넘을 수 없기 때문에 1149까지 세어 120회가 나왔다.
   이제 소스코드 로직을 따라서 이해하면 쉽다.

9. n_arr 은 입력받은 n - 1 까지 0 부터 9의 등장횟수를 저장한다.
   m_arr 은 입력받은 m까지 0 부터 9의 등장횟수를 저장한다.

10. 가장 먼저 1의 자리수에서 0~9까지의 등장횟수를 저장할 것이기 때문에 point 를 1로, n을 -1 해준뒤 n이 0이 아닐 때까지 while 반복을 한다.
    • n % 10 이 9가 아닌 경우, n 의 각 자릿수의 숫자에 해당하는 n_arr 원소값에 point를 더해준다.
      예를 들면, 입력받은 n이 1234 부터 시작하여 1233, 1232, 1231, 1230 까지 각 자릿수에 해당하는 숫자를 point 만큼 올려준다.

- n < 10 인 경우는 오른쪽 끝 부터 확인하여 n //= 10 을 반복해 한자리수가 남았을 때 처리해주는 로직이다. 
  이 경우는 거의 마지막에 해당하는 로직이니 이후에 알아볼 것이다.


- n >= 10 인 경우는 만약 1234 라면 1의 자리를 볼 때, 4 이하는 124번이 등장하며, 5 이상은 123번이 등장한다.
  이는 `(n // 10 + 1) * point` 로 표현할 수 있다.


- 다시 n < 10 인 경우를 보자면, 0부터 n까지의 각 자리에 대해서 point 만큼씩 더해주고, 0인 경우는 point 를 빼준다.
  다른 숫자는 약 130회 등장하는 경우, 0은 120회 등장한다. 직접 계산해보자.

11. 0부터 n - 1 까지 09까지의 등장횟수를 n_arr에 저장했다면, 이제 0부터 m까지 09 등장횟수를 m_arr 에 같은 로직으로 저장한다.

12. 이후는 각자리의 합을 더하는 작업이다.
    n_arr, m_arr 을 순회하면서 각 등장횟수 (m_arr[i] - n_arr[i]) 에 i 를 곱해 ans 에 더해준다.
    이는 각 자리수를 더해주는 것과 같다.

🖥 소스 코드

from sys import stdin

n, m = map(int, stdin.readline().split())

n_arr = [0 for _ in range(10)]
m_arr = [0 for _ in range(10)]

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


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


ans = 0
for i in range(10):
    ans += (m_arr[i] - n_arr[i]) * i

print(ans)

💾 배운점

1. 수학적 사고능력이 필요한 문제였다. 스스로는 이해하기 어려워, 나에게 알고리즘 적으로 도움을 주는 스승이자 동생에게 도움을 받아 이해했다.

2. 각 자리수 별로 0~9의 숫자가 몇 번 등장하는지 계산하는 것은 매우 헷갈리는 작업이었다.

3. 0의 등장횟수는 반드시 다시한번 체크하고 계산해보아야한다. 그렇지 않으면 1019 번 문제를 틀리게 된다.