Algorithm

[BOJ] 1748. 수 이어 쓰기1

프로그래민 2020. 4. 22. 01:02
반응형

브루트 포스 문제이다.

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

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
package online.practice;
 
 
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);
        
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
                                              

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package online.practice;
 
 
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);
    }
}
 
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
                                           
반응형

'Algorithm' 카테고리의 다른 글

[Programmers] 크레인 인형뽑기 게임  (0) 2020.04.27
[SWEA] 5653. 줄기세포배양  (0) 2020.04.27
[BOJ] 6087. 레이저 통신  (0) 2020.04.19
[BOJ] 1107. 리모컨  (0) 2020.04.18
[BOJ] 13023. ABCDE  (0) 2020.04.17