[BOJ] #1748 수 이어 쓰기 1

시간 제한	메모리 제한	정답 비율
1초	128MB	56.357%

1748번: 수 이어 쓰기 1

 

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.
1234567891011121314151617181920212223...
이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

첫째 줄에 N(1≤N≤100,000,000)이 주어진다.

해결

1~n까지 자리수를 계산하여 ans에 일일이 더해주었다.

 

코드

메모리	시간
1984KB	232ms

#include <iostream>
#include <vector>
using namespace std;
typedef long long int ll;
int n;
ll ans;
int main() {
    scanf("%d", &n);
 
    for (int i = 1; i <= n; i++) {
        if (i < 10) ans++;
        else if (i < 100 && i >= 10) ans += 2;
        else if (i < 1000 && i >= 100) ans += 3;
        else if (i < 10000 && i >= 1000) ans += 4;
        else if (i < 100000 && i >= 10000) ans += 5;
        else if (i < 1000000 && i >= 100000) ans += 6;
        else if (i < 10000000 && i >= 1000000) ans += 7;
        else if (i < 100000000 && i >= 10000000) ans += 8;
        else if (i < 1000000000 && i >= 100000000) ans += 9;
    }
 
    printf("%lld", ans);
 
    return 0;
}

 

 

더 좋은 방법

출처: https://www.acmicpc.net/board/view/23735

1 부터 n 까지의 모든 자연수가 그냥 모여있다고 해봅시다.

1의자리수가 존재하는 수는 n개가 있겠죠? 그럼 10의자리수가 존재하는 수는 몇개가 있을까요? 10부터 n까지겠죠? 개수는 n - 10 + 1 개가 될거고요.

마찬가지로 100의자리수가 존재하는 수는 n - 100 + 1 개가 있고요. 이런 식으로 생각해서 죽 더해나간것입니다

메모리	시간
1112KB	0ms

#include<cstdio>
int n, r;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i *= 10)
        r += n - i + 1;
    printf("%d", r);
    return 0;
}