12. 숫자의 총 개수(large : 제한시간 1초)

 

이 문제의 저작권은 인프런 강의 "it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비" 에 있습니다.

 

 

알고리즘 공부를 처음 하게 되면서 원래는 블로그에 정리를 할 생각이 없었는데 점점 난이도가 올라가서 머리 속이 텅텅 휘발됨을 느꼈다...^^; 그래서 블로그에 글을 올림으로써 어려웠던 알고리즘이 좀 더 기억에 오래 남길 하는 바람에 포스팅을 시작한다.

 

 

 

 

 

문제 12

 

자연수 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까지 각 숫자는 몇 개가 사용되었는지를 구하는 프로그램을 작성하세요.

 

 

 

입력예제

 

>> 15

 

 

출력예제

 

>> 21

 

 

 

사고 정리

 

먼저 1 ~ 9 까지는 9개가 존재한다. 두자리 숫자인 10 ~ 99 까지는 (99-10+1)= 90개가 존재한다.

세자리 숫자인 100 ~ 999 까지는 (999-100+1)= 900개가 존재한다.

여기서 규칙은 9, 90, 900, 9000... 이 성립한다는 것을 알 수 있다.

 

문제의 의도는 숫자의 개수를 묻는 문제임으로 개수를 구하게 되면

9 * 1 = 9개

90 * 2 = 180개

900 * 3 = 2700개

....

 

이렇게 되는데 일단 코드를 짤 때 필요한 변수는 9가 필요하겠고 (여기다가 10씩 곱해줄거임) count 변수(1, 2, 3... +1씩 증가)도 필요하겠다. 그리고 위 결과의 개수(9개, 180개, 2700개...)를 누적할 변수 sum 도 있어야겠다(강사님께서 말씀하신 변수는 res였는데 나는 누적하는 변수는 sum이 더 편해서 sum을 사용하겠다)

 

만약 256이라는 숫자를 이용하여 개수를 한 번 구해본다고 생각했을 때, 256은 세자리 숫자이므로 위 계산결과의 두자리까지는 저렇게 하고(180까지) 세자리 숫자부터는 다르게 계산해야 한다.

세자리 숫자는 256 - 99 = 157 개가 존재한다. 이를 곱하기 3을 하면 되겠다. 여기서 세자리 숫자임의 조건은 99보다 커야 되는 것이다. 마찬가지로 다른 자릿수 조건은 9, 99, 999, 9999... 이렇게 커지는 규칙이 있다.

 

 

 

 

 

코드 짜보기

 

#include <stdio.h>
using namespace std;

int main(){
	int n, count=1, d=9, res=0, sum=0, i=9;  // i는 조건을 판별하는 변수
	
	scanf("%d", &n);
	while(i<n){           // i는 조건을 판별. 예를 들어 9, 99<256까지 계산
		res = count*d;    // 숫자의 개수 계산
		sum += res;       // 숫자의 개수를 누적하는 변수 sum
		count++;          
		d=d*10;
		i += d;           // i에 그 다음 조건을 세우기.. 예: i+90=99, i+900=999
	}
	
	i = i-d;              // 위의 조건문에서 i가 n보다 커지면 break되므로 i-d를 다시함
  
	sum += (n-i)*count;  // 누적합에 (256-99)*3 더하기
	
	printf("%d", sum);
	return 0;
}

 

 

너무 헷갈려서 시간이 꽤 오래 걸렸다..

앞으로 규칙들을 생각하고 그 규칙을 이용하여 차근차근 코드를 세워보는 연습을 해야겠다.