문제
자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자는 몇 개 쓰였을까요? 예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 총 21개가 쓰였음을 알 수 있습니다. 자연수 N이 입력되면 1부터 N까지 각 숫자는 몇 개가 사용되었는지를 구하는 프로그램을 작 성하세요.
💡 입력설명
첫 번째 줄에는 자연수 N(3<=N<=100,000,000)이 주어진다.
💡 출력설명
첫 번째 줄에 숫자의 총개수를 출력한다.
💡 입력예제
15
💡 출력예제
21
코드
최종 풀이
#include <stdio.h>
int main () {
int n, i, sum=0, cnt=0, tmp, res=0, mul=1;
scanf("%d", &n);
// 자릿수 파악
tmp = n;
while(tmp > 0) {
tmp /= 10;
cnt++;
}
// 숫자 총 개수
for(i = 1; i <= cnt; i++) {
if(i == cnt) {
sum += i * (n - res);
break;
}
sum += i * (9 * mul);
res += (9 * mul);
mul *= 10;
}
printf("%d", sum);
return 0;
}
설명
사용자로부터 숫자를 입력받고 n에 할당한다.
숫자의 자릿수를 파악하기 위해 몫이 0이 될 때까지 cnt를 1씩 증가한다.
숫자의 총 개수를 구하기 위해 1부터 숫자의 자릿수(cnt)까지 반복하는 for문을 작성한다.
cnt와 같지 않은 경우 해당 자릿수에 해당하는 최대 개수를 sum에 할당하면 되므로 i * 9 * mul(cnt가 1씩 증가하면 10씩 곱해지는 수)를 할당한다. 또한 각 자리수의 최대값들을 누적하기 위해 9 * mul을 res에 할당한 후 mul을 10씩 곱해나간다.
cnt와 같은 경우 각 자리의 개수 i와 사용자로부터 받은 n값에서 각 자리수의 최대값들을 누적한 res를 뺀 값을 곱하고 sum에 더하여 for문에서 빠져나온다.
배운 점
원리를 파악하는데 있어 시간소요가 컸지만 숫자의 자릿 수와 시간복잡도를 줄이기 위한 식을 도출하는데 도움이 되었다.
해당 내용은 김태원님의 'it 취업을 위한 알고리즘 문제풀이' 강의를 듣고 작성한 글입니다.
