백준 1748 - 수 이어 쓰기 1

문제 설명

 

 

=> 브루트 포스 문제입니다. 

=> 모든 숫자를 탐색하며 길이를 재 더할 경우, 시간초과의 늪에 빠지게 됩니다. 

 

 

 

 

<시간초과 code>

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    
    int N;
    cin >> N;
    
    int ans=0;
    for(int i=1; i<=N; i++)
    {
        string str = to_string(i);
        int len = str.length();
        ans += len;
    }
    cout << ans<<'\n';
    }

 

 

 

=>위와 같은 방법이 아닌 계산으로 더하는 방법을 고안해내야합니다. 

 

• 1~9 : 1(숫자의 길이) * 9(해당하는 숫자의 갯수)

• 해당하는 숫자의 갯수 = 끝숫자 - 첫숫자 +1

• 10~99 : 2 * (99-10 +1)

• 100 ~ 999 : 3 * (999-100+1)

• ...

• ...

• ...

 

=> 위와 같은 방법을 활용하여 for문을 통해 계산을 해야합니다. 

 

 

 

 

 

<code>

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    
    int N;
    cin >> N;
    
    long long ans =0;
    for( int start=1, len=1; start <= N; start*=10, len++)
    {
        int end =start*10-1;
        if(end >N)
        {
            end = N;
        }
        ans += (long long)(end - start +1)*len;
    }
    cout <<ans <<'\n';
    return 0;
}

 

 

 

 

 

실행 화면

 

 

시간 초과

---

***잘 안될때는 남의 code를 써보고 디버깅을 하며 이해하는 방법도 나쁘지 않습니다. 
***저는 처음에 이해가 안되어 코드를 쓰고 디버깅을 하며 해당 문제를 이해했습니다.