# 유형 : 탐색, DFS

# 난이도 : 골드 5

# 문제를 이해 못해서 한참 걸렸다.. 그냥 가로세로선에 최대 3개 가로선을 추가하며 1에서 출발해서 1로(2->2, 3->3) 도착하는 사다리를 만드는 것이다. DFS의 전형적인 문제라고 할 수 있다. 0~3개의 가로선을 추가하며 지정한 가로선 개수와 추가한 사다리 개수가 일치할 때 반복문을 돌려 추가한 가로선의 개수로 1->1로 돌아오는지를 체크하면 된다.

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p15684 {
    static final int maxY = 31, maxX = 11;
    static int N,M,H, result;
    static boolean check[][];
    static boolean isTrue = false;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        check = new boolean[maxY][maxX];
        
        for(int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            check[a][b] = true;
        }
        
        for(int i=0; i<=3; i++) {
            result = i;
            dfs(1,0);
            if(isTrue) {
                System.out.println(result);
                return;
            }
        }
        System.out.println("-1");
    }
    private static void dfs(int y, int cnt) {
        // TODO Auto-generated method stub
        if(cnt == result) {
            boolean isPossible = true;
            for(int i=1; i<=N; i++) {
                int col = i;
                for(int j=1; j<=H; j++) {
                    if(check[j][col])
                        col++;
                    else if(col>1 && check[j][col-1])
                        col--;
                }
                
                if(i!=col) {
                    isPossible = false;
                    break;
                }
            }
            if(isPossible)
                isTrue = true;
            return;
        }
        
        for(int i=y; i<=H; i++) {
            for(int j=1; j<N; j++) {
                if(!check[i][j-1] && !check[i][j] && !check[i][j+1]) {
                    check[i][j] = true;
                    dfs(i, cnt+1);
                    check[i][j] = false;
                }
            }
        }
        return;
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2234 성곽 - Java 자바  (0) 2020.03.02
#백준_3987 보이저 1호 - Java 자바  (0) 2020.03.02
#백준_1347 미로 만들기 - Java 자바  (0) 2020.02.29
#백준_2933 미네랄 - Java 자바  (0) 2020.02.27
#백준_5566 주사위 게임 - Java 자바  (0) 2020.02.27

# 유형 : 시뮬레이션, 구현

# 난이도 : 실버 4

# 문제를 처음에 보고 뭐지..했는데 배열의 크기를 최대 100으로 잡고 다 벽으로 채워놓은 다음 중심점을 기준으로 시작하여 F가 나올때마다 전진하고 아닐땐 방향만 돌려주면서 최소 row, col 최대 Row,col을 체크해주면 된다.

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
46
47
48
49
50
51
52
53
54
55
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class p1347 {
    static int moveX[] = {0,1,0,-1};
    static int moveY[] = {-1,0,1,0};
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        
        int row=1, col=1;
        char arr[][] = new char[101][101];
        for(int i=0; i<101; i++) {
            for(int j=0; j<101; j++)
                arr[i][j] = '#';
        }
        int startX, startY, minY, minX, maxY, maxX;
        startX = startY = minY = minX = maxX = maxY = 50;
        int dir = 2;
        arr[startY][startX] = '.';
        for(int i=0; i<str.length(); i++) {
            if(str.charAt(i) == 'F') {
                startX += moveX[dir];
                startY += moveY[dir];
                arr[startY][startX] = '.';
                maxX = Math.max(maxX, startX);
                maxY = Math.max(maxY, startY);
                minX = Math.min(minX, startX);
                minY = Math.min(minY, startY);
            }
            else if(str.charAt(i) == 'L'){
                if(dir == 0)
                    dir = 3;
                else
                    dir--;
            }else {
                if(dir==3)
                    dir=0;
                else
                    dir++;
            }
        }
        
        for(int i=minY; i<=maxY; i++) {
            for(int j=minX; j<=maxX; j++) {
                System.out.print(arr[i][j]);
            }System.out.println();
        }
    }
}
 
 
 cs

'백준' 카테고리의 다른 글

#백준_3987 보이저 1호 - Java 자바  (0) 2020.03.02
#백준_15684 사다리 조작 - Java 자바  (0) 2020.02.29
#백준_2933 미네랄 - Java 자바  (0) 2020.02.27
#백준_5566 주사위 게임 - Java 자바  (0) 2020.02.27
#백준_1135 뉴스 전하기 - Java  (0) 2020.02.26

# 유형 : 시뮬레이션 + 탐색(BFS,DFS)

# 난이도 : 골드 3

# 구현+탐색 문제라서 문제가 어렵기 보다는 코딩하기 좀 복잡했다. 미네랄을 파괴할 때마다 파괴된 미네랄의 4방향 중에 존재하는 클러스터를 탐색(BFS 또는 DFS)로 찾고 각 클러스터에 속하는 부분 원소가 한개라도 바닥에 닿지 않았다면 내리는 작업을 해주면 된다. 문제의 핵심은 클러스터 부분 원소중 한개라도 바닥에 닿을때까지 조건을 따지며 내려주면 된다는 것.

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
package bj;
 
import java.awt.Point;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class p2933 {
    static boolean check = false;
    static ArrayList<Point> cluster = new ArrayList<>();
    static int moveX[] = {0, -1, 0, 1};
    static int moveY[] = {-1, 0, 1, 0};
    static int R,C,N;
    static char arr[][];
    static boolean visit[][];
    static int height[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R][C];
        visit = new boolean[R][C];
        for(int r=0; r<R; r++) {
            String str = br.readLine();
            for(int c=0; c<C; c++) {
                arr[r][c] = str.charAt(c);
            }
        }
        N = Integer.parseInt(br.readLine());
        height = new int[N+1];
        st = new StringTokenizer(br.readLine());
        for(int n=1; n<=N; n++) {
            height[n] = Integer.parseInt(st.nextToken());
            
            boolean left = true;
            int x=-1, y=0;
            
            if(n%2 == 0)
                left = false;
            
            y = R - height[n];
            
            if(left) {
                for(int c=0; c<C; c++) {
                    if(arr[y][c] == 'x') {
                        x = c;
                        break;
                    }
                }
            }else {
                for(int c=C-1; c>=0; c--) {
                    if(arr[y][c] == 'x') {
                        x = c;
                        break;
                    }
                }
            }
            
            if(x == -1)
                continue;
            
            arr[y][x] = '.';
            
            for(int d=0; d<4; d++) {
                int newY = y + moveY[d];
                int newX = x + moveX[d];
                
                if(0<=newY && newY<R && 0<=newX && newX<C && arr[newY][newX] == 'x') {
                    cluster = new ArrayList<>();
                    check = false;
                    visit = new boolean[R][C];
                    
                    cluster.add(new Point(newX, newY));
                    
                    bfs(newY, newX);
                    
                    if(check)
                        continue;
                    
                    while(true) {
                        boolean isPossible = true;
                        
                        for(int i=0; i<cluster.size(); i++) {
                            Point po = cluster.get(i);
                            arr[po.y][po.x] = '.';
                        }
                        for(int i=0; i<cluster.size(); i++) {
                            Point po = cluster.get(i);
                            int nextY = po.y + 1;
                            
                            if(nextY == R || arr[nextY][po.x] == 'x') {
                                isPossible = false;
                                break;
                            }
                        }
                        
                        for(int i=0; i<cluster.size(); i++) {
                            if(isPossible)
                                cluster.get(i).y++;
                            arr[cluster.get(i).y][cluster.get(i).x]='x';
                        }
                        if(!isPossible)
                            break;
                        
                    }
                }
            }
        }
        
        for(int i=0; i<R; i++) {
            for(int j=0; j<C; j++) {
                System.out.print(arr[i][j]);
            }System.out.println();
        }
    }
    
    private static void bfs(int y, int x) {
        // TODO Auto-generated method stub
        Queue<Point> queue = new LinkedList<>();
        queue.add(new Point(x, y));
        visit[y][x] = true;
        while(!queue.isEmpty()) {
            Point po = queue.poll();
            if(po.y == R-1) {
                check = true;
                return;
            }
            
            for(int d=0; d<4; d++) {
                int newY = po.y + moveY[d];
                int newX = po.x + moveX[d];
                
                if(0<=newY && newY<R && 0<=newX && newX<C && !visit[newY][newX] && arr[newY][newX]=='x') {
                    visit[newY][newX] = true;
                    cluster.add(new Point(newX,newY));
                    queue.add(new Point(newX,newY));
                }
            }
        }
    }
    
}
 
 
 cs

'백준' 카테고리의 다른 글

#백준_15684 사다리 조작 - Java 자바  (0) 2020.02.29
#백준_1347 미로 만들기 - Java 자바  (0) 2020.02.29
#백준_5566 주사위 게임 - Java 자바  (0) 2020.02.27
#백준_1135 뉴스 전하기 - Java  (0) 2020.02.26
#백준_2980 도로와 신호등 - Java 자바  (0) 2020.02.26

# 유형 : 구현, 시뮬레이션

# 난이도 : 브론즈 2

# 다이스 굴리고 난 후, 규칙을 적용한 게 한 패턴이라고 생각하고 구현하면 된다.

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
46
47
48
49
50
51
52
53
54
55
56
57
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class p5566 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        // 이 보드 게임의 보드는 N칸으로 이루어져 있고, 출발점은 1칸, 도착점은 N칸이다. 
        // 첫째 줄에 N과 M이 주어진다. M은 상근이가 주사위를 던짓 횟수
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        
        int arr[] = new int[N+1];
        int map[] = new int[N+1];
        int index = 1;
        int count = 0;
        for(int i=1; i<=N; i++) 
            arr[i] = Integer.parseInt(br.readLine());
        
        for(int i=1; i<=M; i++) {
            int dice = Integer.parseInt(br.readLine());
            index += dice;
            count++;
            if(index >= N) {
                System.out.println(count);
                break;
            }
            
            int next = solve(index, arr, N);
            index = next;
            if(index == N) {
                System.out.println(count);
                break;
            }
        }
    }
 
    private static int solve(int index, int arr[], int N) {
        // TODO Auto-generated method stub
        int result = index;
        
        if(arr[index] > 0) {
            result += arr[index];
            if(result > N)
                result = N;
        }else if(arr[index] < 0) {
            result += arr[index];
        }
        
        
        return result;
    }
}
 
cs

'백준' 카테고리의 다른 글

#백준_1347 미로 만들기 - Java 자바  (0) 2020.02.29
#백준_2933 미네랄 - Java 자바  (0) 2020.02.27
#백준_1135 뉴스 전하기 - Java  (0) 2020.02.26
#백준_2980 도로와 신호등 - Java 자바  (0) 2020.02.26
#백준_3048 개미 - Java 자바  (0) 2020.02.25

# 유형 : 탐색, DFS, 그리디

# 난이도 : 플래티넘 5

# 문제를 잘 못 이해해서 한참 걸렸다. 그렇게 생각하다 질문 게시판의 테스트 케이스를 보고 이해하였다.

아래의 테스트케이스 경우에 노드 1의 자식노드는 노드 2보다 많다. 하지만 그림을 그려보면 노드 1보다 노드 2가 깊이가 더 깊게 설계되어있다. 따라서 문제 해결 방식은 상사가 부하에게 전화할 때 가장 오래 걸리는 순으로 정렬한 후 전화를 걸어주면 된다.

1) 무조건 깊다고 그곳으로 들어가는 것이 아니다.

2) 노드 수가 많다고 무조건 그곳이 정답이 아니다.

3) 서브 트리 중 가장 오래 걸리는 순으로 정렬 후, 값을 더해주면서 체크하면 문제를 해결할 수 있다.

 

23

-1 0 1 1 1 2 2 2 3 3 3 4 4 4 0 14 15 16 17 18 19 20 21

 

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
public class p1135 {
    static int N;
    static ArrayList<Point> arrList[];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        arrList = new ArrayList[N];
        for(int i=0; i<N; i++)
            arrList[i] = new ArrayList<>();
        
        st.nextToken();
        
        for(int i=1; i<N; i++) {
            int index = Integer.parseInt(st.nextToken());
            arrList[index].add(new Point(0, i));
        }
        System.out.println(solve(0));
    }
    
    private static int solve(int index) {
        // TODO Auto-generated method stub
        int result = 0; 
        for(int i=0; i<arrList[index].size(); i++) {
            int next = arrList[index].get(i).y;
            arrList[index].get(i).x = 1 + solve(next);
        }
//        for(Point po : arrList[index]) {
//            System.out.print(po.x+" "+po.y+" // ");
//        }System.out.println();
        Collections.sort(arrList[index]);
//        for(Point po : arrList[index]) {
//            System.out.print(po.x+" "+po.y+" // ");
//        }System.out.println();
        for(int i=0; i<arrList[index].size(); i++) {
            arrList[index].get(i).x += i;
            result = Math.max(result, arrList[index].get(i).x);
        }
        return result;
    }
 
    public static class Point implements Comparable<Point>{
        int x;
        int y;
        public Point(int x, int y) {
            this.x=x;
            this.y=y;
        }
        @Override
        public int compareTo(Point o) {
            if(x-o.x>0)
                return -1;
            else if(x-o.x<0)
                return 1;
            return x-o.x;
        }
        
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_2933 미네랄 - Java 자바  (0) 2020.02.27
#백준_5566 주사위 게임 - Java 자바  (0) 2020.02.27
#백준_2980 도로와 신호등 - Java 자바  (0) 2020.02.26
#백준_3048 개미 - Java 자바  (0) 2020.02.25
#백준_1748 수 이어 쓰기 1 - Java 자바  (0) 2020.02.22

# 유형 : 시뮬레이션, 구현

# 난이도 : 실버 3

# 시뮬레이션은 개인마다 푸는 방식이 다른 것 같다. 나의 경우는 매초마다 신호등을 갱신해주면서, 다음 신호등에 도착하였을 때 빨간 불이냐 아니냐를 따지면서 진행하면 된다. 만약 빨간 불인 경우 빨간불의 잔여시간만큼 time을 더해주고 *또 이 time 동안 신호등을 갱신해주면서 진행하면 된다.

 

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package bj;
 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p2980 {
    static int N,L;
    static ArrayList<Po> arrList = new ArrayList<>();
    static ArrayList<Po> tmpList = new ArrayList<>();
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        L = Integer.parseInt(st.nextToken());
        
        for(int n=0; n<N; n++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int r = Integer.parseInt(st.nextToken());
            int g = Integer.parseInt(st.nextToken());
            arrList.add(new Po(w,r,g));
            tmpList.add(new Po(w,r,g));
        }
        int time=0;
        int len = 0;
        int index=0;
        while(len<L && index<N) {
            
            int next = arrList.get(index).where;
            int tmp = len;
            for(int current=tmp+1; current<=next; current++) {
                
                for(int l=0; l<arrList.size(); l++) {
                    if(arrList.get(l).isRed) {
                        if(arrList.get(l).red == 1) {
                            arrList.get(l).red = tmpList.get(l).red;
                            arrList.get(l).isRed = false;
                        }else {
                            arrList.get(l).red--;
                        }    
                    }else {
                        if(arrList.get(l).green == 1) {
                            arrList.get(l).green = tmpList.get(l).green;
                            arrList.get(l).isRed = true;
                        }else {
                            arrList.get(l).green--;
                        }
                    }
                }
                
            }
            
            if(arrList.get(index).isRed) {
                int val = next - len;
                len += val;
                time += val;
                time += arrList.get(index).red;
                int iter = arrList.get(index).red;
                
                for(int i=0; i<iter; i++) {
                    for(int l=0; l<arrList.size(); l++) {
                        if(arrList.get(l).isRed) {
                            if(arrList.get(l).red == 1) {
                                arrList.get(l).red = tmpList.get(l).red;
                                arrList.get(l).isRed = false;
                            }else {
                                arrList.get(l).red--;
                            }    
                        }else {
                            if(arrList.get(l).green == 1) {
                                arrList.get(l).green = tmpList.get(l).green;
                                arrList.get(l).isRed = true;
                            }else {
                                arrList.get(l).green--;
                            }
                        }
                    }
                    
                }
            }else {
                int val = next - len;
                len += val;
                time += val;
            }
            index++;
        }
        time += (L-len);
        System.out.println(time);
    }
    
    public static class Po{
        int where;
        int red;
        int green;
        boolean isRed = true;
        public Po(int w, int r, int g) {
            this.where = w;
            this.red = r;
            this.green = g;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_5566 주사위 게임 - Java 자바  (0) 2020.02.27
#백준_1135 뉴스 전하기 - Java  (0) 2020.02.26
#백준_3048 개미 - Java 자바  (0) 2020.02.25
#백준_1748 수 이어 쓰기 1 - Java 자바  (0) 2020.02.22
#백준_1952 달팽이2 - Java 자바  (0) 2020.02.22

#유형 : 시뮬레이션

# 난이도 : 실버 4

# 간단한 시뮬레이션 문제이다. 리스트를 쓰던, 배열을 쓰던 편한 방식으로 사용하여 해결하면 된다. 이 때 조건은 

 

CBA DEF 를 예를 들어 ABC를 1집단, DEF를 2집단으로 두고, 2집단이 앞으로 오는 경우에는 무시하고 현재 인덱스의 집단이 1집단이면서 현재 인덱스의 집단과 다음인덱스의 집단이 다를 경우에 스왑을 해주면 된다.

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
46
47
48
49
50
51
52
53
54
55
56
57
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
public class p3048 {
    static String str1, str2;
    static ArrayList<Po> arrList = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N1,N2;
        StringTokenizer st = new StringTokenizer(br.readLine());
        N1 = Integer.parseInt(st.nextToken());
        N2 = Integer.parseInt(st.nextToken());
        
        str1 = br.readLine();
        
        for(int i=str1.length()-1; i>=0; i--)
            arrList.add(new Po(str1.charAt(i), 1));
        
        str2 = br.readLine();
        
        for(int i=0; i<str2.length(); i++)
            arrList.add(new Po(str2.charAt(i), 2));
        
        int time = Integer.parseInt(br.readLine());
        
        while(time-- > 0) {
            for(int i=0; i<arrList.size()-1; i++) {
                Po current = arrList.get(i);
                Po next = arrList.get(i+1);
                if(current.num != 2 && current.num != next.num) {
                    arrList.set(i, next);
                    arrList.set(i+1, current);
                    i++;
                }
            }
        }
        for(int i=0; i<arrList.size(); i++)
            System.out.print(arrList.get(i).ch);
    }
    public static class Po{
        char ch;
        int num;
        public Po(char ch, int n) {
            this.ch=ch;
            this.num=n;
        }
    }
}
 
 cs

'백준' 카테고리의 다른 글

#백준_1135 뉴스 전하기 - Java  (0) 2020.02.26
#백준_2980 도로와 신호등 - Java 자바  (0) 2020.02.26
#백준_1748 수 이어 쓰기 1 - Java 자바  (0) 2020.02.22
#백준_1952 달팽이2 - Java 자바  (0) 2020.02.22
#백준_2842 집배원 한상덕 - Java 자바  (0) 2020.02.21

# 유형 : 시뮬레이션

# 난이도 : 실버 3

# 그냥 반복문을 돌리면 시간초과 또는 메모리 초과가 날 것같아서, 자릿수를 이용하는 방식으로 해결하였다. 아래 표는 각 구간의 개수이다. 따라서 일의 자리는 1 * 9, 십의 자리는 2 * 90, 백의 자리는 3 * 900 이런식으로 진행하다가, 마지막 자리수는 음 예를 들어 1542라고 생각해보면 1542 - 1000 + 1 => 543개 마지막 자리수의 단위(1000)를 빼주고 1을 더해준 다음 자릿수(4)를 곱해준다.

1~9 9
10~99 90
100~999 900
1000~9999 9000

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
package bj;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class p1748 {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String num = br.readLine();
        int len = num.length();
        
        int N = Integer.parseInt(num);
        
        int tmp = 9;
        int result = 0;
        for(int i=1; i<len; i++) {
            result += i*tmp;
            tmp*=10;
        }
        
        int last =(int)( N - Math.pow(10, len-1)+1) * len;
        result += last;
        System.out.println(result);
        
    }
}    
 
 cs

'백준' 카테고리의 다른 글

#백준_2980 도로와 신호등 - Java 자바  (0) 2020.02.26
#백준_3048 개미 - Java 자바  (0) 2020.02.25
#백준_1952 달팽이2 - Java 자바  (0) 2020.02.22
#백준_2842 집배원 한상덕 - Java 자바  (0) 2020.02.21
#백준_1331 나이트 투어 - Java 자바  (0) 2020.02.21

+ Recent posts

티스토리툴바