백준 1019번 책 페이지

문제 링크입니다: https://www.acmicpc.net/problem/1019

1019번: 책 페이지

백준님의 풀이 https://www.slideshare.net/Baekjoon/baekjoon-online-judge-1019를 참고하여 코드를 작성했습니다.

 

우선, 주어진 N의 범위가 최대 10억이기 때문에 하나하나 계산하면 TLE가 발생하는 것은 자명합니다.

따라서, 규칙을 찾고 수식을 작성해야하는데 문제를 [A, B] 사이 0 ~ 9 등장 횟수를 세는 것으로 변형시키면 생각보다 간단하게 풀 수 있는 문제였습니다.

A의 일의 자리 숫자가 0이고, B의 일의 자리 숫자가 9라면 그 사이 0 ~ 9가 등장한 횟수는 모두 동일하게 (A/10 - B/10 + 1) 번이 됩니다.

 

따라서 알고리즘은 아래와 같습니다.

1. 초기에 A를 1, B를 N, 그리고 1의 자리 숫자부터 계산하기 때문에 placeOfNum을 1로 설정하고 func 함수를 호출합니다.

2. 기존에 구한 수식을 적용하기 위해 A의 일의 자리 숫자가 0이 될 때까지 A를 1씩 증가시키며 calculate 함수를 호출하고 B의 일의 자리 숫자가 9가 될 때까지 B를 1씩 감소시키며 calculate 함수를 호출시킵니다. 

2.1 A를 증가하고 B를 감소시키는 과정에서는 별다른 수식이 없기 때문에 calculate 함수를 통해 별도로 계산해줍니다.

2.2 기저 사례로 A의 일의 자리 숫자를 0으로 만드는 과정에서 B보다 커지면 B에 대한 처리를 하기 전에 func 함수를 탈출합니다.

3. 2번 과정을 완료했다면 앞서 설명한 (A/10 - B/10 + 1)을 계산하고 placeOfNum을 곱한 값을 각 자리마다 더해줍니다.

4. A와 B를 각각 10으로 나누고 placeOfNum 자리는 10을 곱한 상태에서 2 ~ 3번 과정을 반복합니다.

 

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~