문제
지민이는 N쪽인 책이 한권 있다. 첫 페이지는 1쪽이고, 마지막 페이지는 N쪽이다.
각 숫자가 모두 몇 번이 나오는지 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 출력한다.
예제 입력 11
예제 출력 1 4 1 1 1 1 1 1 1 1
#include <stdio.h>
int main()
{
int num[10] = { 0, };
int tcase, i=1, val;
scanf_s("%d", &tcase);
while (i++ <= tcase)
{
val = i;
while (val){
num[val % 10]++;
val = val / 10;
}
}
for (i = 0; i <= 9; i++)
printf("%d ", num[i]);
}
자꾸 제한시간 초과가 되네요.
여기서 좀더 효율적인 코드로 만드려면 어떻게해야할까요....
가장 간단한 방법은 동적계획법으로... 그런데 수학적으로 더 쉽게 풀 수 있을것 같은데 수학 못해서 잘 모르겠음
예를 들어 N이 9999이면 0000~9999 까지라고 생각하자. 4자리 숫자가 10000개고 중복이 있으니까 4만개가 들어가겠지. 그럼 0~9까지 숫자는 각각 4만을 10으로 나누면 4천개씩 들어감