책 페이지(백준 1019)

1페이지부터 입력받은 페이지 까지 숫자가 총 몇개 나오는지를 출력하는 문제이다.

당연히 하나씩 계산해 나가면 시간초과이기 때문에 방법을 계속 찾았지만, 결국 못찾고 풀이 슬라이드를 참고하였다.

 

https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

Baekjoon Online Judge 1019번 풀이

 

 

문제를 달리 생각해서 A부터 B페이지 까지의 페이지수를 계산하는 개념으로 변경하고 

A는 일의 자리 숫자를 0, B는 일의 자리 숫자를 9로 맞춰주는 것이 중요하다.

0에서 9의 형태를 맞춰주어야 한 셋트씩 숫자를 올려주는 것이 가능하다.

 

여기서 숫자를 올리거나 내려줄때 중요한 개념이 있다.

일의자리를 카운팅 해줄때와 십의자리, 백의자리를 카운팅 해줄때 개념이 달라진다.

일의자리는 한번씩 등장하는 것이지만 십의자리는 10번씩, 백의자리는 백번씩 등장하게 된다.

이에 대해 주의하면서 코드를 살펴보자

 

python

def calc(start, end, ten) :
  count = end // 10 - start // 10 + 1
  for i in range(len(result)):
    result[i] += count * ten

def increase_by_number(num, ten) : # 자리수마다 카운팅 해주는 함수
  k = list(str(num))
  for i in k :
    result[int(i)] += ten
  
def solution(start, end, ten) :
  while(start % 10 != 0 and start <= end) :
    increase_by_number(start, ten)
    start += 1

  if start > end:
    return

  while(end % 10 != 9 and end >= start) :
    increase_by_number(end, ten)
    end -= 1
  calc(start, end, ten)
  solution(start // 10, end // 10, ten * 10)

n = int(input())
result = [0 for _ in range(10)];
solution(1, n, 1)
print(*result)

 

javascript

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().split(' ');
const first = +input[0];
const result = Array.from({length: 10}, (i) => 0)

const calc = (start, end, ten) => {
  count = ~~(end / 10) - ~~(start / 10) + 1
  result.forEach((el, index) => {
    result[index] += count * ten;
  })
}

const increase_by_num = (num, ten) => {
  console.log(num);
  while(num > 0) {
    result[num % 10] += ten;
    num = Math.floor(num / 10);
  }
}

const solution = (start, end, ten) => {
  while(start % 10 !== 0 && start <= end) {
    increase_by_num(start, ten);
    start += 1;
  }

  if (start > end) {
    return;
  }

  while (end % 10 !== 9 && end >= start) {
    increase_by_num(end, ten);
    end -= 1;
  }

  calc(start, end, ten);
  solution(~~(start / 10), ~~(end / 10), ten * 10)
}

solution(1, first, 1);
resultString = ""
for(let i of result) {
  resultString = resultString + i + " ";
}
console.log(resultString)

 

 

 

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

1019번: 책 페이지