백준 1748번 풀이 c++ and java

문제

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 새로운 수의 자릿수를 출력한다.

예제 입력 1 복사

5

예제 출력 1 복사

5

예제 입력 2 복사

15

예제 출력 2 복사

21

예제 입력 3 복사

120

예제 출력 3 복사

252

 

 

구현, 수학 문제이다.

 

처음에는 숫자를 문자열로 바꾼후에 뭇자열의 length를 계속해서 더하는 방식으로 했는데 시간초과가 났다.

다른 문제 풀이 방법을 참고하였다.

 

문제의 로직

1. for문을 돌리는데 i를 ++ 하는게 아니라 *=10씩 해준다.

2. 각 자릿수 갯수를 n-i+1을 이용해서 더해준다.  

(n-1+1 = 1의 자릿수)

(n-10+1 = 10의 자릿수)

(n-100+1 = 100의 자릿수)

(n-1000+1 = 1000의 자릿수)

.

.

 

n-i+1이 잘 이해가 안되시는분들을 위해

 

1~ 550까지의 숫자가 있다고 하자.

이 숫자들을 나열하면 다음과 같을것이다.

 

ex ) 1 , 2 , 3 , 4 ,5  . . .  547 , 548, 549, 550

 

여기에서 1의 자릿수를 계산하면 1,2,3,4,5 ... 547의 5, 548의 5, 549의 5, 550의 5 

이렇게 쭉 하나씩 계산하면 1의 자릿수는 550개이다.

 

그러면 10의 자릿수는?

1~9를 제외한 10부터 550까지 10의 자릿수를 하나씩 계산하면 550-10+1 = 541이다.

 

그러면 100의 자릿수는?

1~9를 제외하고 10~99를 제외하면 550 - 100 + 1 = 451이다. 1~9 = 9개 10~99 = 90개, 9+90 = 99, 550 - 99 = 451

 

이런식으로 구하는것을 n-i+1로 표현해 놓았다고 보면 된다.

 

 

- c++

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



int main() {

    ios_base::sync_with_stdio(false);
    cout.tie(0);
    cin.tie(0);

    int n = 0;
    int ans = 0;
    cin >> n;

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

    cout << ans << "\n";


    return 0;
}

- java

 

java 코드는 거의 유사하기에 생략한다.