C++ 1748 수 이어 쓰기 1

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

시행착오를 많이 겪은 문제라 포스팅하게 되었습니다. 

 

처음에는 자릿수를 구하는 것이므로 간단하게 문자열로 바꿔서 이어붙여야 겠다고 생각했다. 

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    string s;
    for(int i=1; i<=n; i++) {
        s += to_string(i);
    }
    cout << s.size();
}

결과는 메모리 초과가가 뜬다.

 

여기서 막히니까 어떻게 풀어야할지 감이 오지 않았다...

그래서 그냥 있는대로 풀어보았다.

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int ans = 0;
    for(int i=1; i<=n; i++) {
        if(i<=9) {
            ans++;
        }
        else if(i<=99) {
            ans += 2;
        }
        else if(i<=999){
            ans += 3;
        }
        else if(i<=9999){
            ans += 4;
        }
        else if(i<=99999){
            ans += 5;
        }
        else if(i<=999999){
            ans += 6;
        }
        else if(i<=9999999){
            ans += 7;
        }
        else if(i<=99999999){
            ans += 8;
        }
        else
            ans += 9;

    }
    cout << ans;
}

N이 1억이고 시간제한이 0.15 초로 타이트해서 시간초과가 뜬다.

 

결국 마지막에 풀이를 찾아보니 너무 쉬웠다. 왜 이 생각을 못했지...했던 문제

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    int ans = 0;
    for(int i=1; i<=n; i*=10) {
        ans += n-i+1;
    }
    cout << ans;
}

i=1일 때 일의 자리를 가지는 수의 개수를 더한다.

i=10일 때 십의 자리를 가지는 수의 개수를 더한다.

... 

i=n일 때 까지 반복

 

예를 들어 120이면

i=1일 때 1~120까지 모두 일의 자리를 가지므로 120을 더한다. 

i=10일 때 10~120까지 십의 자리를 가지는 수이므로 111을 더한다.

i=100일 때 100~120까지 백의 자리를 가지는 수이므로 21을 더한다.

 

n=100,000,000이 되도 for문은 9번 밖에 돌지 않으므로 시간제한안에 충분히 해결가능하다.