백준 1748 수 이어 쓰기 1

문제 링크: https://www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

120을 예로 들면, 1부터 120까지 120개의 수가 적어도 한자리씩은 차지한다. 10부터 120까지 120 - 9 = 111개의 수가 적어도 두자리씩은 차지한다. 그리고 100 부터 120까지 120 - 9 - 90 = 21개의 수가 적어도 세자리씩은 차지한다. 따라서 120 + 111 + 21 = 252라는 답을 구할수 있다.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    int ans = 0;
    int cnt = 9;
    while(n > 0) {
        ans += n;
        n -= cnt;
        cnt *= 10;
    }
 
    cout << ans << '\n';
    return 0;
}
 

재귀함수 연습할겸 위의 로직을 이용하여 아래와 같이 구현해봤다.

#include <bits/stdc++.h>
using namespace std;
 
int solve(int n, int cnt) {
    if(n - cnt <= 0) return n;
    return n + solve(n - cnt, cnt * 10);
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int n;
    cin >> n;
 
    cout << solve(n, 9) << '\n';
    return 0;
}