1748 수 이어 쓰기 1

수 이어 쓰기 1(1748)

 

풀이코드

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <string>
using namespace std;
// 1748 수 이어 쓰기 1
const int MAX = 40000;


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
	int N;
	
	cin >> N;
	/*
	1 자리 9개
	2 자리 90개
	3 자리 900개
	*/
	
	int tmp = N;
	int len = 0;
	while(tmp){
		tmp /= 10;
		len++;
	}	
	
	int ans = 0;
	for(int i = 0; i < len; i++){
		
		if(i < len - 1) ans += 9 * pow(10, i) * (i + 1);
		else if(i == len - 1){
			ans += len * (N - pow(10, i) + 1);
		}
			
	}
	cout << ans << '\n';
	
	
	
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

 

풀이

태어나서 처음으로, 한 번 코딩에 정답을 찾은 문제이다.

1. N 의 max 가 1억인데, 시간 제한은 0.15초이므로 그저 브루트 포스를 적용하는 것으로는 시간 초과를 받겠다.

2. 그렇다면 중복되는 계산을 줄여야겠다. 여기서의 중복되는 계산은 같은 자리 수는 같은 길이를 늘린다는 점이었다. (2자리수는 2개의 길이를 차지)

3. 120 이 input 이라면 

 

1 자리수 9개

2 자리수 90개

까지 더한 뒤, (중복 계산 줄이기)

3번째 자리수인 100 ~ 120 까지는 브루트 포스를 시행해준다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점