(C++) - 백준(BOJ) 1748번 : 수 이어 쓰기 1

www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

수학문제였습니다.

 

풀이방법

 1. 단순 반복문으로는 시간초과 또는 메모리 초과를 맛볼 수 있으니 자릿수가 달라지는 구간에 대해 수학적으로 접근해야 합니다.

 

 2. n이 1 ~ 9까지는 자리수가 1개씩 더해집니다. 10 ~ 99까지는 자리수가 2개씩 더해집니다. 100 ~ 999까지는 자리수가 3개씩 더해집니다. 따라서 n의 자리수만큼 loop를 돌며 해당하는 값을 적절히 더해주면 됩니다.

 

Code

#include<iostream>
#include<string>
using namespace std;
int ans, margin, behind = 9, after = 1;

int main(){
	string n;
	cin >> n;
	for (int i = 1; i < n.size(); i++){
		ans += behind * i;
		behind *= 10;
		after *= 10;
	}
    margin = (stoi(n) - after + 1) * n.size();
	cout << ans + margin << endl;
}