[백준/Python] 1019번: 책 페이지

https://www.acmicpc.net/problem/1019

1019번: 책 페이지

---

---

문제 분석

단순 N 페이지까지 반복하면서 페이지를 문자열로 변환 후 각 페이지에 존재하는 숫자만큼 등장 횟수를 누적하기가 기본적인 알고리즘일테지만 이 문제의 N의 범위는 10억 이하이기 때문에 시간 초과(시간 복잡도: O(n²))가 나오게 된다.

 

수학적인 접근이 필요한데 이는 백준 사이트의 최백준님의 자료를 참고하여 해결했다.

우선 각 자릿수 별로 등장 횟수를 쪼개서 생각해야 한다.

 

위의 자료에서는 1~N 페이지가 아닌 A~B 페이지를 기준으로 설명하였기 때문에

1~N 페이지로 다시 예를 들자면, 페이지가 39까지 존재한다고 가정해보자.

 

1의 자리의 경우 [1 ~ 9]까지 존재하고,

10의 자리의 경우 [10 ~ 39]까지 존재한다.

 

자릿수를 구분하기 위해 시작 페이지를 구분할 변수가 필요하고 이 시작 페이지 변수의 일의 자리는 0이 되어야 한다.

그리고 마지막 페이지(n)은 일의 자리 수가 9가 되어야 한다.

 

=> start, n이라고 가정할 때

start, n = 0, 9

start, n = 10, 99

...

자릿수 별로 이런 식으로 증가하게 될 것이다.

하지만 이로써도 이해하기가 어렵다.

 

큰 예시를 기준으로 두고 계산해보자 (n = 377)

 

하나하나 분석해보자면 마지막 페이지를 기준으로 마지막 페이지의 일의 자리 숫자가 9가 될 때까지 등장 횟수를 누적하면서 페이지를 감소시킨다.

마지막 페이지는 시작 페이지보다 작아질 수 없기 때문에 (start <= n) 조건이 필요하다.

start, point = 1, 1
num = [0 for _ in range(10)]

while n % 10 != 9 and start <= n:
    num[n] += point
    n -= 1

위와 같은 코드를 구현했을 경우 최종적으로 n은 369가 될 것이다.

하지만 등장 횟수를 누적하기에는 num[n]에서 인덱스가 올바르지 않다.

이를 해결하기 위해서는 감소하면서 변하는 n을 주목하자.

n은 377부터 376, 375, 374, ..., 369가 되는데 각각 수마다 등장 횟수를 누적해야 하기 때문에 377을 10씩 나누면서 나머지가 되는 수의 등장 횟수를 누적해야 한다.

 

def calc(x, num, point):
    while x > 0:
        num[x % 10] += 1
        x //= 10

위의 코드를 통해 377은 num[7], num[7], num[3] 순으로 등장 횟수가 증가한다.

위와의 과정을 통해 370~377페이지의 등장 횟수를 처리했다.

 

남은 1~369페이지의 계산은 어떻게 되는지 알아보면

일의 자리 숫자인 0은 36번, 1부터 9까지의 수는 37번 등장한다.

 

n을 활용하여 369를 10으로 나눈 몫인 36번 증가시킬 수 있다.

=> (10~19, 20~29, 30~39, ..., 350~359, 360~369)

n //= 10

for i in range(10):
    num[i] += n * point

 

하지만 이 경우 1~9페이지의 계산이 이루어지지 않는다.

이를 해결하기 위해 시작 페이지를 증가시켜 자릿수가 증가하는 일의 자리 숫자가 0이 되지 않을 때까지 증가하며 누적하는 것이다.

 

일의 자리가 1부터 9까지 증가하기 위해서는 start 변수를 늘려가면서 체크를 해준다.

while start % 10 != 0 and start <= n:
    num[start] += point
    start += 1

 

위의 코드를 통해 증가하는 값은 1~9까지와 10~369까지 각각 0은 36번, 나머지는 37번 증가하게 된다.

 

하지만 위의 코드에 순서를 중요하게 생각해주어야 한다.

36번 증가시키기 위해 n을 10으로 나눈 몫으로 선언하였기 때문에 아래의 start 변수가 n보다 작을 때 실행되는 코드가 올지 않게 종료되기 때문이다.

 

최종적인 순서는 아래와 같다.

def calc(x, num, point):
    while x > 0:
        num[x % 10] += point
        x //= 10


start, point = 1, 1

while True:
    # 마지막 페이지를 일의 자리가 9가 될 때까지 줄이며 등장 횟수 누적
    while n % 10 != 9 and start <= n:
        calc(n, num, point)
        n -= 1
	
    # 종료 조건
    if n < start:
        break

    # 시작 페이지를 일의 자리가 0이 될 때까지 늘리며 등장 횟수 누적
    while start % 10 != 0 and start <= n:
        calc(start, num, point)
        start += 1
	
    # 최종적인 계산을 위해 start를 10을 나눠줌
    start //= 10
    
    # n을 10으로 나눈 몫으로 일의 자리가 몇 번 등장하는지 누적
    n //= 10

    for i in range(10):
        num[i] += n * point

 

1. 종료 조건의 경우

n이 만약 7과 같은 한자리 숫자일 경우, 9가 되기 위해 1씩 감소하지만 최종적으로 0까지 감소하게 된다.

이는 start보다 작은 값이기 때문에 여기서 반복을 종료해야 문제 없이 종료가 된다.

 

2. start를 10으로 나누는 이유

start는 항상 1~9 페이지의 등장을 확인해야 하기 때문에 10까지 증가했던 start를 다시 1로 만들어주어야 한다.

 

3. 마지막으로 가장 중요한 포인트

위에서 등장 횟수를 누적하기 위해 point라는 변수를 사용했는데 이를 쓴 이유는

n의 일의 자리 숫자를 파악하기 위해서 10이라는 수로 계속 나누어주기 때문에

377이라는 예제에서는 369를 거쳐 36이 되고 29를 거쳐 2가 된다.

 

36은 사실상 360이라는 수를 의미하기 때문에 36이 29가 되는 과정에서 36이 10번, 35가 10번, ..., 29가 10번 등장하게 되는 것이다. => 일의 자리 숫자를 제외한 나머지 숫자는 고정적으로 10번씩 등장한다.

따라서 point에 10을 곱해 자릿수가 증가할 때마다 등장 횟수를 10의 제곱수만큼 늘려서 누적해주어야 한다.

 

---

간단한 39의 예제를 위와 같이 표현할 수 있다.

 

---

 

코드

n = int(input())

num = [0 for _ in range(10)]


def calc(x, num, point):
    while x > 0:
        num[x % 10] += point
        x //= 10


start, point = 1, 1

while True:
    while n % 10 != 9 and start <= n:
        calc(n, num, point)
        n -= 1

    if n < start:
        break

    while start % 10 != 0 and start <= n:
        calc(start, num, point)
        start += 1

    start //= 10
    n //= 10

    for i in range(10):
        num[i] += n * point

    point *= 10

print(*num)

---

 

최종적인 리뷰로 단순해보이면서 복잡한 문제였다고 생각한다. 나름대로 이해한만큼 내용을 작성하려고 노력했지만 이 글을 읽는 독자들은 이해가 잘 안되는 부분이 있을 수 있다고 느낀다.

 

혹시라도 질문이 있다면 자유롭게 댓글 남겨주시면 추가적인 설명을 해드리겠습니다.