[BOJ] 1748. 수 이어 쓰기1

브루트 포스 문제이다.

그러나 단순 브로트포스로 풀게되면 시간초과가 생기기 때문에 최적화를 시키고 풀어야한다. 다음과 같이 풀수 있다.
N=120
- 1 ~ 9 => (9 - 1 +1) X 1
- 10 ~ 99 => (99 - 10 +1) X 2
- 100 ~ 120 => (120 - 100 +1) X 3

package online.practice;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_1748_수이어쓰기1 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num=Integer.parseInt(br.readLine());
        
        int compare=100;
        int answer=0;
        
 
        if(num<10) {
            System.out.println(num);
            return;
        }
        
        answer=9;
        int len=2;
        while(true) {
            if(num < compare) {
                answer+=((num)- (compare/10) +1)*len;
                break;
            }
            
            answer+= ((compare-1) - (compare/10) +1)*len;
            compare=compare*10;
            len=len+1;
        }
        
        System.out.println(answer);
        
    }
}
 

 

 

package online.practice;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main_bj_1748_수이어쓰기1_re {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int num=Integer.parseInt(br.readLine());
        
        long ans = 0;
        for (int start=1, len=1; start<=num; start*=10, len++) {
            int end = start*10-1;
            if (end > num) {
                end = num;
            }
            ans += (long)(end - start + 1) * len;
        }
        System.out.println(ans);
    }
}