'Algorithm/백준' 카테고리의 글 목록

Algorithm/백준

백준 2798번 블랙잭

헤헿헿 2021. 8. 22. 21:11

2021. 8. 22. 21:11

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

2798번: 블랙잭

첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장

www.acmicpc.net

기본적인 완전탐색 문제다.

알고리즘이 너무 오랜만이라 다 까먹어서 처음부터 다시 공부하는 느낌으로 풀었다.

다 풀고나서 다른 사람의 풀이를 보니 재귀함수를 다르게 구현하면 코드가 훨씬 간단해진다는 것을 알고 씁쓸해졌다..

소스코드

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

import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    static int m, answer=0;
    static int[] card;
    static ArrayList<Integer> indexAr = new ArrayList<Integer>();
    
    static public void recur(int n, int toPick) {
        if(toPick==0) {
            compare();
            return;
        }
        int smallest = indexAr.isEmpty() ? 0 : indexAr.get(indexAr.size()-1) + 1;
        
        for(int i= smallest; i<n; i++) {
            indexAr.add(i);
            recur(n, toPick-1);
            indexAr.remove(indexAr.size()-1);
        }
    }
    
    public static void compare() {
        int tot=0, al = indexAr.size();
    
        for(int i=0; i<al; i++) {
            tot += card[indexAr.get(i)];
        }
        if (tot > m) return;
 
        answer = Math.max(answer, tot);
    }
 
    public static void main(String[] args) {
        int n;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        card = new int[n];
        
        for(int i=0; i<n; i++) {
            card[i] = sc.nextInt();
        }
        
        recur(n, 3);
        System.out.println(answer);
    }
}
Colored by Color Scripter

cs

저작자표시

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

백준 17144번 미세먼지 안녕! (0)	2019.05.03
백준 16235번 나무재테크 (0)	2019.05.03
백준 15685번 드래곤 커브 (0)	2019.05.02
백준 14891번 톱니바퀴 (0)	2019.04.30
백준 15683번 감시 (0)	2019.04.30

백준 17144번 미세먼지 안녕!

헤헿헿 2019. 5. 3. 22:54

2019. 5. 3. 22:54

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

문제 접근

1. T번 동안 먼지를 확산시키고 공기청정기를 작동시키는걸 반복 한 후 남은 먼지의 양을 구해서 출력해주었다.

소스 코드

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
import java.util.Scanner;
 
public class Main {
    
    static int r, c, t, upY=-1, downY;
    static int map[][];
    static int dy[] = { 0, 0, 1, -1 };
    static int dx[] = { 1, -1, 0, 0 };
    
    public static void cycle() {
        // 위쪽꺼
        for(int i=upY-1; i>0; i--) {
            map[i][0] = map[i-1][0];
        }
        for(int i=0; i<c-1; i++) {
            map[0][i] = map[0][i+1];
        }
        for(int i=0; i<upY; i++) {
            map[i][c-1] = map[i+1][c-1];
        }
        for(int i=c-1; i>1; i--) {
            map[upY][i] = map[upY][i-1];
        }
        // 한칸 채우기
        map[upY][1] = 0;
        
        //아래쪽꺼
        for(int i = downY+1; i<r-1; i++) {
            map[i][0] = map[i+1][0];
        }
        for(int i=0; i<c-1; i++) {
            map[r-1][i] = map[r-1][i+1];
        }
        for(int i=r-1; i>downY; i--) {
            map[i][c-1] = map[i-1][c-1];
        }
        for(int i=c-1; i>1; i--) {
            map[downY][i] = map[downY][i-1];
        }
        map[downY][1] = 0;
    }
    
    public static void diffusion() {
        int tmpmap[][] = new int[r][c];
        tmpmap[upY][0] = -1;
        tmpmap[downY][0] = -1;
        
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(map[i][j]<=0) continue;
                
                int difcnt = 0;
                int difsu = map[i][j] / 5;
                for(int d=0; d<4; d++) {
                    int ny = i + dy[d];
                    int nx = j + dx[d];
                    
                    if(ny<0 || nx<0 || ny>=r || nx>=c) continue;
                    if(map[ny][nx] == -1) continue;
                    
                    tmpmap[ny][nx] += difsu;
                    difcnt++;
                }
                tmpmap[i][j] += map[i][j] - (difcnt*difsu);
            }
        }
        
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                map[i][j] = tmpmap[i][j];
            }
        }
    }
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        r = sc.nextInt();
        c = sc.nextInt();
        t = sc.nextInt();
        
        map = new int[r][c];
        
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                int tmpInt = sc.nextInt();
                map[i][j] = tmpInt;
                if(tmpInt == -1) {
                    if(upY == -1) {
                        upY = i;
                    }
                    else {
                        downY = i;
                    }
                }
            }
        }
        
        for(int i=0; i<t; i++) {
            diffusion();
            cycle();
        }
        
        int sum = 0;
        for(int i=0; i<r; i++) {
            for(int j=0; j<c; j++) {
                if(map[i][j]<=0) continue;
                
                sum += map[i][j];
            }
        }
        
        System.out.println(sum);
        
    }
}
Colored by Color Scripter
cs

저작자표시

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

백준 2798번 블랙잭 (0)	2021.08.22
백준 16235번 나무재테크 (0)	2019.05.03
백준 15685번 드래곤 커브 (0)	2019.05.02
백준 14891번 톱니바퀴 (0)	2019.04.30
백준 15683번 감시 (0)	2019.04.30

백준 16235번 나무재테크

헤헿헿 2019. 5. 3. 22:44

2019. 5. 3. 22:44

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

문제 접근

1. 각 칸마다 나무가 몇 그루가 들어갈지 모르므로 각 칸마다 ArrayList를 만들어 주어 나무를 추가하였다.

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
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
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    static int n, m, k, cnt=0;
    static int a[][], yb[][];
    static ArrayList<Namoo> nar[][];
    static int dy[] = { 0, 0, 1, -1, 1, 1, -1, -1 };
    static int dx[] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        
        a = new int[n+1][n+1];
        yb = new int[n+1][n+1];
        nar = new ArrayList[n+1][n+1];
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                a[i][j] = sc.nextInt();
                yb[i][j] = 5;
                nar[i][j] = new ArrayList<Namoo>();
            }
        }
        
        for(int i=0; i<m; i++) {
            int y = sc.nextInt();
            int x = sc.nextInt();
            int z = sc.nextInt();
            
            nar[y][x].add(new Namoo(z, true));
        }
        
        for(int g=0; g<k; g++) {
            //봄
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    for(int l=0; l<nar[i][j].size(); l++) {
                        if(nar[i][j].get(l).age<=yb[i][j]) {
                            yb[i][j] -= nar[i][j].get(l).age;
                            nar[i][j].get(l).age++;
                        }
                        else {
                            nar[i][j].get(l).alive = false;
                        }
                    }
                }
            }
            //여름
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    for(int l=nar[i][j].size()-1; l>=0; l--) {
                        if(nar[i][j].get(l).alive==false) {
                            yb[i][j] += (nar[i][j].get(l).age/2);
                            nar[i][j].remove(l);
                        }
                    }
                }
            }
            
            //가을
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    for(int l=0; l<nar[i][j].size(); l++) {
                        if(nar[i][j].get(l).age%5==0) {
                            for(int d=0; d<8; d++) {
                                int ny = i + dy[d];
                                int nx = j + dx[d];
                                
                                if(ny<1 || nx<1 || ny>n || nx>n) continue;
                                
                                nar[ny][nx].add(0, new Namoo(1, true));
                            }
                        }
                    }
                }
            }
            
            //겨울
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    yb[i][j] += a[i][j];
                }
            }
        }
        
        
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                cnt += nar[i][j].size();
            }
        }
        
        System.out.println(cnt);
        
    }
}
 
class Namoo{
    int age;
    boolean alive;
    Namoo(int age, boolean alive) {
        this.age = age;
        this.alive = alive;
    }
}
Colored by Color Scripter
cs

저작자표시

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

백준 2798번 블랙잭 (0)	2021.08.22
백준 17144번 미세먼지 안녕! (0)	2019.05.03
백준 15685번 드래곤 커브 (0)	2019.05.02
백준 14891번 톱니바퀴 (0)	2019.04.30
백준 15683번 감시 (0)	2019.04.30

백준 15685번 드래곤 커브

헤헿헿 2019. 5. 2. 21:51

2019. 5. 2. 21:51

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

x, y 좌표의 최대 범위가 <=100 이였는데 문제 대충읽고 <100으로 알고 풀었다.

그래서 런타임에러와 틀렸습니다를 반복하며 맞왜틀 맞왜틀 하다가 범위를 다시 확인하고 맞았다.

문제 접근

1. 드래곤 커브의 정보를 입력받았다.

2. 드래곤 커브의 세대를 진행해주었다

각 드래곤커브의 정보는 ArrayList로 유지하였고 드래곤 커브가 위치하고 있는 점은 map배열에 표시해주었다.

3. map배열을 순회하며 정사각형의 네 꼭지점이 모두 드래곤커브의 일부인 정사각형의 개수를 세어 출력하였다.

소스 코드

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
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    static boolean map[][] = new boolean[101][101];
    static int generation[];
    static ArrayList<Point> curve[];
    static int dy[] = { 0, -1, 0, 1 };
    static int dx[] = { 1, 0, -1, 0 };
    
    public static void rotate(int index) {
        int curveSize = curve[index].size();
        Point lastP = curve[index].get(curveSize-1);
        
        for(int i=curveSize-2; i>=0; i--) {
            Point tmp = curve[index].get(i);
            int yDif = lastP.y - tmp.y;
            int xDif = lastP.x - tmp.x;
            
            int nextY = lastP.y - xDif;
            int nextX = lastP.x + yDif;
            
            curve[index].add(new Point(nextY, nextX));
            map[nextY][nextX] = true;
        }
        
    }
    
    public static void main(String[] args) {
        int n, x, y, d, g, cnt=0;
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        generation = new int[n];
        curve = new ArrayList[n];
        
        // 입력, 0세대 커브 만듦
        for(int i=0; i<n; i++) {
            x = sc.nextInt();
            y = sc.nextInt();
            d = sc.nextInt();
            g = sc.nextInt();
            
            curve[i] = new ArrayList<Point>();
            
            curve[i].add(new Point(y, x));
            map[y][x] = true;
            int ny = y + dy[d];
            int nx = x + dx[d];
            curve[i].add(new Point(ny, nx));
            map[ny][nx] = true;
            
            generation[i] = g;
        }
        
        for(int i=0; i<n; i++) {
            if(generation[i]>0) {
                for(int j=0; j<generation[i]; j++) {
                    rotate(i);
                }
            }
        }
        
        for(int i=0; i<100; i++) {
            for(int j=0; j<100; j++) {
                if(map[i][j] && map[i+1][j] && map[i][j+1] && map[i+1][j+1])
                    cnt++;
            }
        }
        System.out.println(cnt);
    }
}
 
class Point {
    int y;
    int x;
    Point(int y, int x) {
        this.y = y;
        this.x = x;
    }
}
Colored by Color Scripter
cs

저작자표시

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

백준 17144번 미세먼지 안녕! (0)	2019.05.03
백준 16235번 나무재테크 (0)	2019.05.03
백준 14891번 톱니바퀴 (0)	2019.04.30
백준 15683번 감시 (0)	2019.04.30
백준 14889번 스타트와 링크 (0)	2019.04.28

백준 14891번 톱니바퀴

헤헿헿 2019. 4. 30. 20:50

2019. 4. 30. 20:50

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

소스 코드

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
 
public class Main {
    
    static ArrayList<Integer> ar[] = new ArrayList[5];
    static int hb[] = new int[5];
    
    public static void rotate(int num, int d) {
        int tmp;
        if(d>0) {
            // 시계
            tmp = ar[num].get(7);
            ar[num].remove(7);
            ar[num].add(0, tmp);
        }
        else if (d<0){
            // 반시계
            tmp = ar[num].get(0);
            ar[num].remove(0);
            ar[num].add(tmp);
        }
    }
    
    
    public static void solve(int num, int d) {
        Arrays.fill(hb, 0);
        
        hb[num] = d;
        
        //오른쪽 봄
        for(int i = num; i<4; i++) {
            if((ar[i].get(2) + ar[i+1].get(6))==1)
                hb[i+1] = hb[i]*-1;
            else
                break;
        }
        
        //왼쪽봄
        for(int i=num; i>1; i--) {
            if((ar[i].get(6) + ar[i-1].get(2))==1)
                hb[i-1] = hb[i]*-1;
            else
                break;
        }
        
        //회전시킴
        for(int i=1; i<5; i++) {
            rotate(i, hb[i]);
        }
        
    }
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        for(int i=0; i<5; i++) {
            ar[i] = new ArrayList<Integer>();
            if(i==0) continue;
            String s = sc.nextLine();
            
            for(int j=0; j<8; j++) {
                ar[i].add(s.charAt(j) - '0');
            }
        }
        
        int k = sc.nextInt();
        
        int num, d;
        
        for(int j=0; j<k; j++) {
            num = sc.nextInt();
            d = sc.nextInt();
            solve(num, d);
        }
        
        int ans=0;
        
        for(int i=1; i<5; i++) {
            if(ar[i].get(0)==1) {
                int hapsu = 1;
                for(int j=1; j<i; j++) {
                    hapsu *=2;
                }
                ans += hapsu;
            }
        }
        
        System.out.println(ans);
    }
    
}
Colored by Color Scripter
cs

저작자표시

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

백준 16235번 나무재테크 (0)	2019.05.03
백준 15685번 드래곤 커브 (0)	2019.05.02
백준 15683번 감시 (0)	2019.04.30
백준 14889번 스타트와 링크 (0)	2019.04.28
백준 14890번 경사로 (0)	2019.04.28

백준 15683번 감시

헤헿헿 2019. 4. 30. 20:27

2019. 4. 30. 20:27

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

문제 접근

1. 완전탐색으로 cctv의 방향이 바뀌는 모든 경우를 체크하여 사각지대가 가장 적은 경우의 사각지대 수를 출력하였다.

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
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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
import java.util.ArrayList;
import java.util.Scanner;
 
public class Main {
    
    static int[][] map;
    static int n, m, mincnt;
    static ArrayList<Cctv> ar = new ArrayList<Cctv>();
    static int[] dy = { -1, 0, 1, 0 };
    static int[] dx = { 0, 1, 0, -1 };
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        n = sc.nextInt();
        m = sc.nextInt();
        
        map = new int[n][m];
        
        mincnt = n*m;
        
        for(int i=0; i<n; i++) {
            for(int j=0; j<m; j++) {
                int t = sc.nextInt();
                map[i][j] = t;
                if(t>=1 && t<=5) {
                    ar.add(new Cctv(i, j, t));
                }
            }
        }
        
        recur(0);
        
        System.out.println(mincnt);
    }
    
    static void recur(int index) {
        if(index==ar.size()) {
            int cnt=0;
            
            for(int i=0; i<n; i++) {
                for(int j=0; j<m; j++) {
                    if(map[i][j]==0) cnt++;
                }
            }
            
            if(mincnt > cnt)
                mincnt = cnt;
            
            return;
        }
        
        Cctv tmp = ar.get(index);
        
        switch (tmp.cctvType) {
        case 1 :
            
            for(int i=0; i<4; i++) {
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                fillcctv(tmp.y, tmp.x, i);
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
            
            break;
            
        case 2 :
            
            for(int i=0; i<2; i++) {
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                fillcctv(tmp.y, tmp.x, i);
                fillcctv(tmp.y, tmp.x, i+2);
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
            
            break;
            
        case 3 :
            
            for(int i=0; i<4; i++) {
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                fillcctv(tmp.y, tmp.x, i);
                if(i==3)
                    fillcctv(tmp.y, tmp.x, 0);
                else
                    fillcctv(tmp.y, tmp.x, i+1);
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
                
            break;
            
        case 4 : 
            
            for(int i=0; i<4; i++) {
                
                int[][] tmpmap = new int[n][m];
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        tmpmap[j][k] = map[j][k];
                    }
                }
                
                for(int j=0; j<4; j++) {
                    if(i==j) continue;
                    fillcctv(tmp.y, tmp.x, j);
                }
                
                recur(index+1);
                
                for(int j=0; j<n; j++) {
                    for(int k=0; k<m; k++) {
                        map[j][k] = tmpmap[j][k];
                    }
                }
            }
            
            break;
            
        case 5 : 
            
            for(int j=0; j<4; j++) {
                fillcctv(tmp.y, tmp.x, j);
            }
            
            recur(index+1);
            
        }
        
        
        
    }
    
    
    static void fillcctv(int y, int x, int d) {
        switch(d) {
        
        case 0 :
            for(int i = y-1; i>=0; i--) {
                if(map[i][x]==6) break;
                if(map[i][x]>=1 && map[i][x]<=5) continue;
                
                map[i][x] = 9;
            }
            
            break;
            
        case 1 :
            for(int i=x+1; i<m; i++) {
                if(map[y][i]==6) break;
                if(map[y][i]>=1 && map[y][i]<=5) continue;
                
                map[y][i] = 9;
            }
            break;
            
        case 2 :
            for(int i=y+1; i<n; i++) {
                if(map[i][x]==6) break;
                if(map[i][x]>=1 && map[i][x]<=5) continue;
                
                map[i][x] = 9;
            }
            break;
            
        case 3 :
            for(int i=x-1; i>=0; i--) {
                if(map[y][i]==6) break;
                if(map[y][i]>=1 && map[y][i]<=5) continue;
                
                map[y][i] = 9;
            }
            
            break;
        }
    }
    
}
 
 
class Cctv {
    int y;
    int x;
    int cctvType;
    
    Cctv(int y, int x, int cctvType) {
        this.y = y;
        this.x = x;
        this.cctvType = cctvType;
    }
}
Colored by Color Scripter
cs

저작자표시

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

백준 15685번 드래곤 커브 (0)	2019.05.02
백준 14891번 톱니바퀴 (0)	2019.04.30
백준 14889번 스타트와 링크 (0)	2019.04.28
백준 14890번 경사로 (0)	2019.04.28
백준 14503번 로봇 청소기 (0)	2019.04.27

백준 14889번 스타트와 링크

헤헿헿 2019. 4. 28. 17:40

2019. 4. 28. 17:40

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

문제 접근

1. 재귀를 통해 팀이 이루어지는 모든 경우의 수를 완전탐색하였다.

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <iostream>
#include <vector>
 
using namespace std;
 
int n, halfN, minans = 99999;
int s[50][50];
bool selectN[50];
 
vector <int> trueTeam;
vector <int> falseTeam;
 
void recur(int minimumNum, int toPick) {
    if (toPick == 0) {
 
        trueTeam.clear();
        falseTeam.clear();
 
        // 처리
        for (int i = 0; i < n; i++) {
            if (selectN[i] == true)
                trueTeam.push_back(i);
            else
                falseTeam.push_back(i);
        }
        
        int ttsum=0, ftsum=0;
 
        for (int i = 0; i < trueTeam.size(); i++) {
            for (int j = 0; j < trueTeam.size(); j++) {
                if (i == j) continue;
 
                ttsum += s[trueTeam[i]][trueTeam[j]];
 
            }
        }
 
        for (int i = 0; i < falseTeam.size(); i++) {
            for (int j = 0; j < falseTeam.size(); j++) {
                if (i == j) continue;
 
                ftsum += s[falseTeam[i]][falseTeam[j]];
            }
        }
 
        int chai = ttsum > ftsum ? ttsum - ftsum : ftsum - ttsum;
 
        if (minans > chai)
            minans = chai;
 
        return;
    }
 
    for (int i = minimumNum; i < n; i++) {
        selectN[i] = true;
        recur(i + 1, toPick - 1);
        selectN[i] = false;
    }
 
}
 
int main()
{
    cin >> n;
    halfN = n / 2;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> s[i][j];
    
    recur(0, halfN);
 
    cout << minans;
 
}
Colored by Color Scripter
cs

저작자표시

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

백준 14891번 톱니바퀴 (0)	2019.04.30
백준 15683번 감시 (0)	2019.04.30
백준 14890번 경사로 (0)	2019.04.28
백준 14503번 로봇 청소기 (0)	2019.04.27
백준 14888번 연산자 끼워넣기 (0)	2019.04.27

백준 14890번 경사로

헤헿헿 2019. 4. 28. 16:53

2019. 4. 28. 16:53

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

문제 접근

1. 코드 작성을 편하게 하기 위해 2차원배열에 들어있는 값들을 한줄씩 살펴 볼때마다, 한줄을 1차원배열에 복사하여 지나갈 수 있는 길인지 체크하였다.

2. 체크하는 과정은 우선 한길에 속한 모든 칸의 높이가 같은지를 먼저 확인하고 만약 모든칸의 높이가 같다면 지나갈 수 있는 길로 판단하였다.

3. 이후엔 복사해놓은 배열을 앞에서 뒤로 탐색하며 인접 칸의 높이 차이를 구하였다.

높이의 차이가 2이상이면 지나갈수 없는길로 판단했다.

높이의 차이가 1이라면 차이가 나기 시작한 점부터 l만큼의 길이에 있는 점들이 같은 높이 인지 판단하였다.

만약 l만큼길이의 점들중 다른 높이가 하나라도 있다면 지나갈수 없는 길로 판단했다.

l만큼의 길이의 점들이 모두 같은 높이라면 오른쪽아래로 내려가는 경사로를 놓았다.

경사로를 놓는 것은 bool 배열을 이용하여 해당 인덱스의 값을 true로 바꾸어 주었다.

4. 3번과 마찬가지로 뒤에서 앞으로 탐색하며 지나갈수있는길인지 경사로를 놓을수 있는지를 판단한 후 왼쪽 아래로 내려가는 경사로를 놓았다.

왼쪽아래로 내려가는 경사로도 마찬가지로 다른 bool 배열을 이용하여 체크하였다.

5. 오른쪽 아래로 내려가는 경사로와 왼쪽 아래로 내려가는 경사로를 체크한 두 배열을 비교하며 경사로가 겹치는 부분이 있으면 지나갈수 없는길로 판단하였다.

겹치는 부분이 없으면 지나갈 수 있는길로 판단하였다.

6. 모든 길에 대해 1번~5번의 과정을 거치며 지나갈수 있는길인지 없는 길인지를 판단하며 지나갈수 있는 길의 경우 그 수를 세어 마지막에 출력하였다.

소스코드

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
#include <iostream>
 
using namespace std;
 
int map[100][100];
int clonline[100];
int n, l, cnt = 0;
 
bool rgsr[100];
bool lgsr[100];
 
bool isSameHeight(int s, int e) {
    for (int i = s; i < e; i++) {
        if (clonline[i] != clonline[i + 1]) {
            return false;
        }
    }
    return true;
}
 
void inspection(int ay, int ax, int by, int bx) {
    // 클론 배열 복사
    if (ay == by) {
        // y좌표 같음 가로로 봄.
        for (int i = 0; i < n; i++) {
            clonline[i] = map[ay][i];
        }
    }
    else if (ax == bx) {
        // x좌표 같음 세로로 봄.
        for (int i = 0; i < n; i++) {
            clonline[i] = map[i][ax];
        }
    }
 
    // 1. 높이 다 같은 경우
    if (isSameHeight(0, n - 1)) {
        cnt++;
        return;
    }
 
    // 경사로 배열 초기화
    for (int i = 0; i < n; i++) {
        rgsr[i] = false;
        lgsr[i] = false;
    }
 
    int differ;
 
    //앞에서 뒤로 탐색
    for (int i = 0; i < n-1; i++) {
        differ = clonline[i] - clonline[i + 1];
        if (differ > 1) {
            return;
        }
        else if (differ == 1) {
            int e = i + l;
            if (e >= n)
                return;
 
            if (isSameHeight(i + 1, e)) {
                // 경사로 설치
                for (int j = i + 1; j <= e; j++) {
                    rgsr[j] = true;
                }
            }
            else {
                return;
            }
        }
    }
 
    //뒤에서 앞으로 탐색
    for (int i = n - 1; i > 0; i--) {
        differ = clonline[i] - clonline[i - 1];
        if (differ > 1)
            return;
        else if (differ == 1) {
            int s = i - l;
            if (s < 0)
                return;
 
            if (isSameHeight(s, i - 1)) {
                //경사로 설치
                for (int j = s; j <= i - 1; j++) {
                    lgsr[j] = true;
                }
            }
            else {
                return;
            }
        }
    }
 
    for (int i = 0; i < n; i++) {
        if (rgsr[i] && lgsr[i]) {
            return;
        }
    }
 
    cnt++;
 
}
 
int main()
{
    cin >> n >> l;
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> map[i][j];
 
 
    for (int i = 0; i < n; i++) {
        inspection(i, 0, i, n - 1);
    }
 
    for (int j = 0; j < n; j++) {
        inspection(0, j, n - 1, j);
    }
 
    cout << cnt;
}
Colored by Color Scripter
cs

저작자표시

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

백준 15683번 감시 (0)	2019.04.30
백준 14889번 스타트와 링크 (0)	2019.04.28
백준 14503번 로봇 청소기 (0)	2019.04.27
백준 14888번 연산자 끼워넣기 (0)	2019.04.27
백준 14500번 테트로미노 (0)	2019.04.26

PREV 이전 1 2 3 4 NEXT 다음

BBLOG