백준 [1748] 수 이어 쓰기 1(Java)

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

1748번: 수 이어 쓰기 1

완전 탐색

1부터 N까지의 수를 문자형 형태로 만들어 이어붙인뒤, 그 길이를 구한다.
하지만, 제한 시간이 c++ 기준 0.15초 이내로 풀어야 하고
메모리 제한도 128MB이기 때문에, 시간과 메모리 초과가 발생한다.

 

완전 탐색 최적화 - N의 탐색 범위 최소화

수를 나열해보면 다음 결과를 도출할 수 있다.
- 1부터 N 까지의 수는 모두 일의 자리를 가지고 있다.
- 만약, N이 10 이상이면, N - 9 개의 십의 자리를 가지고 있다. (1 ~ 9 총 9개)
- 만약, N이 100 이상이면 N - 99 개의 백의 자리를 가지고 있다. (1 ~ 9 총 9개, 10 ~ 99 총 90개)
이를 통해 수식을 만들면 다음과 같다.

answer += N - i + 1 (i = 1, i는 10씩 곱해짐)

 

파이썬에선 루프 범위와 증감을 자유롭게 사용하는게 어려워서 자바를 썼다.

 

코드

import java.io.*;

class Main {

    static int N;
    static StringBuffer answer = new StringBuffer();

    public static void main(String[] args) throws Exception {
        input();
        solve();
        print();
    }

    private static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
    }

    private static void solve() {
        int ans = 0;
        for (int i = 1; i <= N; i *= 10) {
            ans += (N - i + 1);
        }
        answer.append(ans);
    }


    private static void print() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(answer.toString());
        bw.flush();
    }
}