기술 블로그

1748번 수 이어 쓰기 1 본문

알고리즘 문제/BOJ

1748번 수 이어 쓰기 1

parkit 2020. 1. 12. 13:45
728x90
반응형

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




길이가 1인 숫자의 개수 : 9 - 1 + 1 = 9개

길이가 2인 숫자의 개수 : 99 - 10 + 1 = 90개

길이가 3인 숫자의 개수 : 999 - 100 + 1 = 900

길이가 4인 숫자의 개수 : 9999 - 1000 + 1 = 9000개


길이가 1인 숫자들의 길이의 합 = 1 * 9개 = 9

길이가 2인 숫자들의 길이의 합 = 2 * 90개 = 180

길이가 3인 숫자들의 길이의 합 = 3 * 900개 = 2700

길이가 4인 숫자들의 길이의 합 = 4 * 9000개 = 36000



위위 규칙은 x 20, x 300, x 4000 이런 식의 곱하기 연산임을 알 수 있다.



(이제부터 예시를 통해 설명)



예를 들어, N = 120이라고 하자.


120은 길이가 3인 자연수이다.


그렇다면 일단 


길이가 1인 숫자들의 길이의 합과 길이가 2인 숫자들의 길이의 합을 누적하자.


9 + 180 = 189이다. (number_length() 함수)



120은 길이가 3인 숫자이므로, 길이가 3인 숫자의 제일 첫 숫자를 구해보자.(make_number() 함수)


길이가 3인 숫자의 제일 첫 숫자는 100이다.


100 ~ 120은 총 21개이다.(120 - 100 + 1)



그리고 길이가 3이므로, 3 * 21개 = 63이다.



따라서, 답은 189 + 63 = 252가 나온다.







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.io.*;
import java.util.*;
 
public class Main {
    
    static int number_length(int pivot)
    {
        int ret = 0;
        
        for(int i=1, j=1; i<=pivot; i++, j*=10) {
            ret += i*j*9;
        }
        
        return ret;
    }
    
    static int make_number(int len)
    {
        int ret = 1;
        
        for(int i=0; i<len-1; i++) {
            ret *= 10;
        }
        
        return ret;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
 
        String s = br.readLine();
        int n = Integer.parseInt(s), ans = 0;
        
        ans += number_length(s.length() - 1);
        
        int g = make_number(s.length());
        
        ans += (n - g + 1)*s.length();        
 
        bw.write(String.valueOf(ans + "\n"));    
        bw.flush();
        bw.close();
    }
}
cs



















728x90
반응형

'알고리즘 문제 > BOJ' 카테고리의 다른 글

18242번 네모네모 시력검사  (0) 2020.01.13
1780번 종이의 개수  (0) 2020.01.13
3049번 다각형의 대각선  (0) 2020.01.10
1911번 흙길 보수하기  (0) 2020.01.10
1459번 걷기  (0) 2020.01.10