백준# 1019 - 책 페이지

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

1019번: 책 페이지

재귀 알고리즘으로 분류된 1019번 책 페이지 문제 입니다.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace _1019
{
    class Program
    {
        public static Dictionary<int, long> countDict;
        public static string page;
 
        public static void RecurPage(int index, int digit)
        {
            int leftNum = (index == 0) ? 0 : int.Parse(page.Substring(0, index));
            int rightNum = (index == page.Length - 1) ? 0 : int.Parse(page.Substring(index + 1));
            int indexNum = int.Parse(page.Substring(index, 1));
 
            //0 포함하는 갯수 구하기.
            for(int i = 0; i < 10; i++)
            {
                if(i > indexNum)
                {
                    countDict[i] += leftNum * digit;
                }
 
                else if(i == indexNum)
                {
                    countDict[i] += ((leftNum * digit) + rightNum + 1);
                }
 
                else
                {
                    countDict[i] += (leftNum + 1) * digit;
                }
            }
 
            //0갯수 제거.
            countDict[0] -= digit;
 
            if (index == 0)
                return;
 
            else
                Program.RecurPage(index - 1, digit * 10);
        }
 
        static void Main(string[] args)
        {
            Program.countDict = new Dictionary<int, long>();
            Program.page = Console.ReadLine();
            for (int i = 0; i < 10; i++)
                Program.countDict.Add(i, 0);
 
            Program.RecurPage(Program.page.Length - 1, 1);
 
            for (int i = 0; i < 9; i++)
                Console.Write(Program.countDict[i] + " ");
            Console.Write(Program.countDict[9]);
        }
    }
}
 

저는 책 페이지가 주어졌다면 그것을 1의자리 부터 가장 높은 자릿수까지 재귀를 돌렸습니다.

각 자릿수에서 0부터 9까지 몇번 등장 할지를 구해 딕셔너리에 넣었습니다.

 

참고로 0을 고려하지 않고 나중에 빼줬습니다.

예를들어  100페이지 에서 001쪽은 나올 수 없으나 0갯수 두개를 그냥 더하고 나중에 0갯수를 따로 빼주었습니다.

 

ex) 527

527을 전역 변수로 저장하고 7과 자릿수의 값(1의 자리는 1, 10의 자리는 10)을 넣었습니다.

 

1. 1의자리에서 0부터 9까지 몇번 등장하는지 확인합니다.

leftNum은 52가 됩니다. 일의 자리에서 0부터 9까지 52번 반복되고 520 ~ 527까지 일의자리가

0부터 7까지 하나씩 더 나옵니다.

 

2. 10의자리에서 0부터 9까지 몇번 등장하는지 확인합니다.

leftNum : 5, rightNum : 7입니다

2보다 큰 수는 50번 등장하며 2는 50번에 520  ~ 527까지 8번 더 등장합니다.

1과 0은 51번 등장합니다.

 

3. 100의 자리에서 0부터 9까지 몇 번 등장하는지 같은 방법으로 확인합니다.

 

 

마지막으로 있을 수 없는 0의 갯수를 일의자리부터 고려합니다.

1의 자리에서는 의미없는 0이 000 만 가능합니다.

10의 자리에서는 000 ~ 009까지 가능합니다.

100의자리 에서는 000 ~ 099까지 가능합니다.

 

이를 계산해 마지막에 0의 갯수를 줄여주면 되겠습니다.