[BOJ] 1019 책 페이지

1019번: 책 페이지

문제

지민이는 전체 페이지의 수가 N인 책이 하나 있다. 첫 페이지는 1 페이지이고, 마지막 페이지는 N 페이지이다. 각 숫자가 전체 페이지 번호에서 모두 몇 번 나오는지 구해보자.

입력

첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다.

---

문제의 지문이 너무 긴 것도 별로지만 너무 짧아도 문제에 손이 잘 안 간다. 심지어 이 문제는 누가 봐도 어떠한 규칙을 찾는 문제인 것 같아서 평소 같았으면 풀지 않았을 것이다. 그런데 요새 하도 조건이 줄줄줄 달려있는 문제만 풀다 보니 이런 심플한 문제도 풀어보고 싶어서 골랐다.

 

그냥 단순히 1부터 시작해서 등장하는 숫자들을 세어가면 풀 수도 있는 문제다. 하지만 N이 최대 10억까지 들어올 수 있는 관계로 제한 시간인 2초 안에는 절대 불가능하다. 대충 연산 1억번에 1초 걸린다고 생각하면 10초 이상이 걸린다. 따라서 어떠한 규칙을 찾아내야만 한다. 이런 수학 카테고리 문제에 잼병이라 도움을 받고자 구글을 켰더니 무려 백준 님의 자료가 있어서 이걸 참고했다.

 

Baekjoon Online Judge 1019번 풀이

 

아마 내가 직접 이 아이디어를 생각해내려고 했으면 매일매일 고민해서 2년 정도 걸렸을 것 같다. 이 아이디어의 핵심은  1부터 N 사이에 등장하는 숫자들을 센다로 주어진 문제를 A부터 B 사이에 등장하는 숫자들을 센다로 바꾸는 것이다. 오히려 문제가 더 난해해진 것 같았지만 다 이유가 있었다. 

 

그러고나서 A의 일의 자릿수를 0으로, B의 일의 자릿수를 9로 만든다. 이 과정에서는 어쩔 수 없이 등장하는 숫자들을 일일이 세어줘야 한다. 그래서 calc라는 함수를 만들어서 A++, B--를 하는 동안의 숫자들을 셌다. 이렇게 A, B를 조작하게 되면 A와 B 사이에 등장하는 숫자들을  A/10 - B/10 + 1로 한 번에 셀 수 있게 된다. 더 자세한 내용은 링크에서 볼 수 있다.

 

그다음엔 재귀 호출을 사용해서 A/10, B/10 사이의 등장하는 숫자들을 세면 된다. 하지만 이때 사실 실제 숫자는 10을 곱해야 하기 때문에 A/10, B/10 사이에 등장하는 숫자 개수에도 10을 곱해야 한다. 이렇게 해서 A랑 B가 같아질 때까지 계속 재귀 호출을 부르다 보면 정답을 구할 수 있다.

 

 

후기)

문제를 풀던 도중에 함수 인자와 for문 조건을 건 변수를 똑같이 써서 답이 제대로 나오지 않았었다. 이런 작은 코드에서도 이런 실수를 하는데 더 큰 코드를 쓰게 되면 변수를 제대로 다르게 써서 프로그램을 관리할 수 있도록 하자. 

 

이런 아이디어 하나만으로 팍! 풀리는 문제를 풀었더니 속이 뻥 뚫린다.