[AtCoder - ABC029 D] 1

난이도: 1393

 

태그

• Recursion
• Divide and Conquer

 

풀이

1. 어떤 수 \( N \)에 있는 1의 개수를 세보자.

\( N \)에 있는 1의 개수는, \( N \)을 계속 10으로 나누면서 1의 자리가 1인지 계속 봐주면 됩니다.

 

2. [1]을 조금 다르게 생각해보자.

[1]에서 구하는 과정을 잘 생각해보면, (10 이상의 자리에 있는 1의 개수) + (1의 자리에 있는 1의 개수)로 표현할 수 있습니다.

 

3a. \( 0 \) 이상 \( N \) 이하의 모든 정수에 있는 1의 개수를 세는 방법

\( f(n) \)를 \( 0 \) 이상 \( n \) 이하의 모든 정수에 있는 1의 개수라고 정의하고

\( g(n) \)을 \( n \)에 있는 1의 개수라고 정의해봅시다.

 

그럼, \( f(n) = f(n-1) + g(n) \)이라는 간단한 재귀식을 찾아볼 수 있습니다.

 

3b. \( 0 \) 이상 \( N \) 이하의 모든 정수에 있는 1의 개수를 [2]를 사용해 좀 더 빠르게 세는 방법

10 이상의 자리에 들어가는 수는 \( 0 \) 이상 \( \left\lfloor \frac{N}{10} \right\rfloor \)가 됩니다.

그리고 이 수는 10가지 다른 1의 자리와 묶이므로 10번씩 등장하게 됩니다.

// 엄밀히는 마지막 수는 10번 미만 등장할 수는 있습니다. 이는 [4]에서 다룰 예정입니다.

즉, \( 10 \times f(\left\lfloor \frac{N}{10} \right\rfloor) \)가 됩니다.

 

1의 자리는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, ...라는 주기 10의 간단한 규칙을 가지고 있으므로,

이를 토대로 생각해보면 등장 횟수는 \( \left\lfloor \frac{N+9}{10} \right\rfloor \)회가 됩니다.

 

즉, \( f(N) = 10 \times f(\left\lfloor \frac{N}{10} \right\rfloor) + \left\lfloor \frac{N+9}{10} \right\rfloor \)입니다...?

 

4. [3a]와 [3b]를 묶어보자.

3b의 주석에서 말했듯이, 10 이상의 자리에 들어가는 수를 계산할 때 마지막 수는 10번 등장하지 않을 수 있습니다.

이를 처리하기는 귀찮으니, 실제로 마지막 수도 10번씩 등장할 때만 위 식을 사용해봅시다.

 

마지막 수까지 10번 등장하기 위해서는, \( N = 10n + 9 \) 꼴이어야 합니다.

그러니 이 경우만 [3b]로 처리해줍시다.

 

다른 경우에는 그냥 [3a]로 처리해줘도 충분히 빠른 시간에 돕니다.

\( f \)가 10번 돌 때마다 /10이 되므로 log 시간이 유지되기 때문이죠.

 

5. 코드

코드에서는 \( \left\lfloor \frac{N+9}{10} \right\rfloor \)가 아니라 \( \left\lfloor \frac{N+1}{10} \right\rfloor \)을 더해줬는데, \( N = 10n + 9 \)에서 동일한 값을 가지므로 걱정하지 않아도 됩니다.

앳코더의 옛날 문제는 출력이 NewLine으로 끝나지 않으면 WA 처리하므로 주의하세요!