백준 1748 수 이어 쓰기 1

백준 1748 수 이어 쓰기 1

문제보기

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

수를 n 까지 이어쓰는데, n까지 이어썼을 때 총 길이가 몇인지 세는 것이다.

그래서 나는 len 함수를 만들어서 일일히 길이를 다 더해주기로 생각했다.

함수는 log10 n 의 시간복잡도를 가지고, 총 n번 반복하니, n* logn 의 시간복잡도를 가지는 풀이이다. 

좀더 멋진 풀이 방법이 있긴하다. 시간복잡도는 n이다.

for 문을 딱 1번 1~n까지 순회하는데, i가 1~9까지는 1씩 길이가 더해지고, 10~99 까지는 2씩 길이를 더해준다.

이렇게 하려면 

int base = 10, cnt=1, ans=0;

for (int i=1; i<=n; i++){

    if ( i== base){ 

       base*=10;

       cnt++;

    }

    ans+=cnt;

}

정도로 구현할 수 있다.

하지만 brute force 방법도 유효하다라는 점을 생각해봤으면 좋겠다. 굉장히 직설적인 풀이라 초보자들에게 좋은 사고법을 제시해주는 것같다.

소스보기

https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1748.cc