백준 1748 수 이어 쓰기 1

알고리즘 문제/Brute Force

gaelim 2018. 1. 26. 02:05

문제보기

수를 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 방법도 유효하다라는 점을 생각해봤으면 좋겠다. 굉장히 직설적인 풀이라 초보자들에게 좋은 사고법을 제시해주는 것같다.