공부흔적

문제 링크

오답 ) 완전탐색

  처음에는 완전탐색을 이용해서 풀었다.

  하지만 완전 탐색을 할 경우 최대 입력인 10억이 입력값으로 들어오는 경우

  반복문을 10억번 돌고, 또 안에서 숫자의 길이에 따라 반복문을 돌기 때문에 시간초과가 나게된다.

#include <cstdio>
#include <string.h>
using namespace std;

int main(void)
{
	int n, i, j, tmp, cnt[10] = {0};

	scanf("%d", &n);
	for(i = 1; i <= n; i++){
		char buf[11] = "";
		sprintf(buf, "%d", i);
		for(j = 0; j < strlen(buf); j++)
			cnt[buf[j]-'0']++;
	}
	for(i = 0; i < 10; i++)
		printf("%d ", cnt[i]);
	return 0;
}

  정답 ) 시간 문제를 해결하기 위해서 숫자에 따라 규칙성을 찾았다.

    0을 시작으로해서 9까지 각 숫자가 1의 자리에서 쓰일 때, 10의 자리에서 쓰일 때, ..., 각각 나누어서 더해주었다.

  225를 예로 2가 쓰이는 횟수를 세어보면 다음과 같다.

  1. j = 0 (1의 자리에서 쓰이는 2의 개수)

    cnt[2] += 225 / 10 * 1 (=22) : 2, 12, 22, ..., 212

    if 225 / 1 % 10 (1의 자리 수) > 2 -> cnt[2] += 1 : 222

    j = 1 (10의 자리에서 쓰이는 2의 개수)

    cnt[2] += 225 / 100 * 10 (=20) : 20~29, 120~129

    if 225 / 10 % 10 (10의 자리 수) == 2 -> cnt[2] += 225 % 10 + 1 (=6) : 220~225

    j = 2 (100의 자리에서 쓰이는 2의 개수)

    cnt[2] += 225 / 1000 * 100 (=0)

    if 225 / 100 % 10 (100의 자리 수) == 2 -> cnt[2] += 225 % 100 + 1 (=26) : 200 ~ 225

#include <cstdio>
#include <cmath>	// pow()
using namespace std;

int main(void)
{
  int n, len = 1, cnt[10] = {0, };
  scanf("%d", &n);
  int tmp = n;
  while(tmp/=10)
    len++;
  for(int i = 0; i < 10; ++i)
    for(int j = 0; j < len; ++j){
      double tmpd1 = pow(10.0, (double)j);
      double tmpd2 = pow(10.0, (double)(j+1));
      int tmp1 = (int)tmpd1;
      int tmp2 = (int)tmpd2;
      int tmp = n/tmp1%10;

      cnt[i] += (n/tmp2-(i==0?1:0)) * tmp1;
      if(tmp == i)
        cnt[i] += n%tmp1+1;
      else if(tmp > i)
        cnt[i] += tmp1;
    }
  for(int i = 0; i < 10; ++i)
    printf("%d ", cnt[i]);
  return 0;
}

주의점 )

  - 0의 쓰임을 확인할 때 주의해야한다.

    위의 예에서 2같은 경우 10의 자리를 확인할 때 20~29, 120~129를 확인했지만

    0의 경우 두자리인 00~09는 불가능하기 때문에 코드에서 처음 cnt[i]에 더해줄 때 0인지 확인하는 조건을 추가했다.

  - pow( ) 의 경우 반환형이 double이기 때문에 바로 사용했을 때 문제가 발생할 수 있다.

    (int)pow(10, 2)를 출력했을 때 99가 나오는 등 값이 정확하지 않아서 코드에서 다소 지저분하게 처리했다.