문제 링크 : 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);
    }
}
 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

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42626

 

단순하게 배열이나 리스트를 사용하여 소팅하면 시간 초과가 나는 문제였다.

우선순위 큐를 사용하여 풀었다.

 

소스코드

 

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
import java.util.Collections;
import java.util.PriorityQueue;
 
class Solution {
    public int solution(int[] scoville, int K) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for(int i=0; i<scoville.length; i++) {
            pq.add(scoville[i]);
        }
        
        while(true) {
            if(pq.peek()>=K) break;
            if(pq.size()==1) {
                answer = -1;
                break;
            }
            
            int t1 = pq.poll();
            int t2 = pq.poll();
            int t3 = t1 + (t2*2);
            pq.add(t3);
            answer++;
        }
        
        return answer;
    }
}
cs

 

저작자표시


문제 링크 : 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);
        
    }
}
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


문제 링크 : 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;
    }
}
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


문제 링크 : 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;
    }
}
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


문제 링크 : 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);
    }
    
}
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


문제 링크 : 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;
    }
}
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


문제 링크 : 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;
 
}
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

+ Recent posts

티스토리툴바