실3 1748 수 이어 쓰기 1 - 브루트포스 건너뛰며해보기

https://www.acmicpc.net/problem/1748

1748번: 수 이어 쓰기 1

 

//수 이어 쓰기1
public void bf_1748(String[] args) throws IOException {
    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.valueOf(bf.readLine());
    long ans = 0;

    // 직접 계산하는 방법도 가능하지만, N이 너무 크기 때문에 실제로 수를 모두 만들면 시간초과
    // ex) 999까지 그냥 구하면 => 시행횟수가 999이지만, 자릿수로 하면 1자리,2자리,3자리 => 시행횟수가 3
    // 1억 = 9자리 => 9번만 구하면 됨

    // 1. 자릿수가 1일때 범위는 1~9이다.
    // len=1 => 초기 자릿수 1
    // start=1 => 초기값 1

    // 2. 자릿수가 2일때 범위는 10~99이다.
    // len++ => 자릿수 1씩 증가
    // start*=10 => 초기값 1에서 10배씩 증가

    // 3. end = start*10 -1 => end는 다음 자릿수의 start에서 1을 빼준값과 같다.

    // 4. start<=n => 최대 시행횟수
    // end = n => end가 n보다 처음 주어진 수보다 클 경우, 처음 주어진 수를 end로 변경한다
    // ex) 150까지 구하기면 3자릿수의 최대값인 999까지 전부 구할 필요 없이 150까지만 구하면 된다.

    // 5. ans += (long)(end - start + 1) * len;
    // (end - start + 1) => len 자리 수의 개수
    // * len => len 자리의 자릿 수
   for (int start=1, len=1; start<=n; start*=10, len++) {
        int end = start*10 -1;
        if (end > n) {
            end = n;
        }
        ans += (long)(end - start + 1) * len;
    }
    System.out.println(ans);
}