문제 출처:https://www.acmicpc.net/problem/14697


 문제


정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 개 있다. 정보 초등학교에서는 학생들에게 이 방들을 배정하되, 배정된 모든 방에 빈 침대가 없도록 하고자 한다.

예를 들어, 방의 종류가 5인실, 9인실, 12인실이고 6학년 여학생 전체가 113명 이라면, 5인실 4개, 9인실 5개, 12인실 4개를 예약하면 각 방에 남는 침대 없이 배정이 가능하다. 또한 12인실은 사용하지 않고 5인실 10개와 9인실 7개만 사용하는 것도 가능하다. 그러나 방의 종류가 3인실, 6인실, 9인실이고 6학년 여학생 전체가 112명이라면 빈 침대 없이 방을 배정하는 것은 불가능하다.

방의 정원을 나타내는 서로 다른 세 자연수와 전체 학생 수를 나타내는 자연수 하나가 주어졌을 때, 배정된 모든 방에 빈 침대가 없도록 방 배정이 가능한지를 결정하는 프로그램을 작성하시오. 단, 세 종류의 방은 모두 충분한 개수가 있다고 가정하며, 위의 예에서와 같이 세 종류의 방을 모두 활용하지 않고 한 종류 또는 두 종류의 방만 이용하여 배정하는 것도 허용한다.


 입력


표준 입력으로 방의 정원을 나타내는 서로 다른 세 자연수 A, B, C (1 ≤ A < B < C ≤ 50)와 전체 학생 수를 나타내는 자연수 N (1 ≤ N ≤ 300)이 공백으로 분리되어 한 줄에 주어진다.


 출력


빈 침대 없이 배정이 가능할 경우 표준 출력으로 1을, 불가능할 경우 0을 출력한다.


문제의 입력이 크지 않기 때문에 모든 경우O(n^3)를 탐색해도 시간안에 충분히 문제를 풀 수 있습니다.


따라서 재귀나 3중 포문을 이용하여 문제를 풀 수 있는데 저는 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
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <ctime>
#include <string.h>
 
using namespace std;
 
int main(void)
{
    int a, b, c, n, check = 0;
    scanf("%d %d %d %d", &a, &b, &c, &n);
    for (int k = 0; k < (n / c + 1); k++) {
        for (int i = 0; i < (n / b + 1); i++) {
            for (int j = 0; j < (n / a + 1); j++) {
                if ((k*c) + (i*b) + (j*a) == n)
                    check = 1;
            }
        }
    }
    printf("%d", check);
    return 0;
}
cs



저작자표시

'알고리즘 문제 > 브루트 포스' 카테고리의 다른 글

[백준] 15683번: 감시 - C++  (0) 2018.07.20
[백준] 15686번:치킨 배달 - C++  (0) 2018.07.19

문제 출처:https://www.acmicpc.net/problem/15683


 문제


스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감시할 수 있는 방법은 다음과 같다.

1번2번3번4번5번

1번 CCTV는 한 쪽 방향만 감시할 수 있다. 2번과 3번은 두 방향을 감시할 수 있는데, 2번은 감시하는 방향이 서로 반대방향이어야 하고, 3번은 직각 방향이어야 한다. 4번은 세 방향, 5번은 네 방향을 감시할 수 있다.

CCTV는 감시할 수 있는 방향에 있는 칸 전체를 감시할 수 있다. 사무실에는 벽이 있는데, CCTV는 벽을 통과할 수 없다. CCTV가 감시할 수 없는 영역은 사각지대라고 한다.

CCTV는 회전시킬 수 있는데, 회전은 항상 90도 방향으로 해야 하며, 감시하려고 하는 방향이 가로 또는 세로 방향이어야 한다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0

지도에서 0은 빈 칸, 6은 벽, 1~5는 CCTV의 번호이다. 위의 예시에서 1번의 방향에 따라 감시할 수 있는 영역을 '#'로 나타내면 아래와 같다.

0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 # 6 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
# # 1 0 6 0
0 0 0 0 0 0
0 0 # 0 0 0
0 0 # 0 0 0
0 0 1 0 6 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 6 0
0 0 # 0 0 0
→←↑↓

CCTV는 벽을 통과할 수 없기 때문에, 1번이 → 방향을 감시하고 있을 때는 6의 오른쪽에 있는 벽을 감시할 수 없다.

0 0 0 0 0 0
0 2 0 0 0 0
0 0 0 0 6 0
0 6 0 0 2 0
0 0 0 0 0 0
0 0 0 0 0 5

위의 예시에서 감시할 수 있는 방향을 알아보면 아래와 같다.

0 0 0 0 0 #
# 2 # # # #
0 0 0 0 6 #
0 6 # # 2 #
0 0 0 0 0 #
# # # # # 5
0 0 0 0 0 #
# 2 # # # #
0 0 0 0 6 #
0 6 0 0 2 #
0 0 0 0 # #
# # # # # 5
0 # 0 0 0 #
0 2 0 0 0 #
0 # 0 0 6 #
0 6 # # 2 #
0 0 0 0 0 #
# # # # # 5
0 # 0 0 0 #
0 2 0 0 0 #
0 # 0 0 6 #
0 6 0 0 2 #
0 0 0 0 # #
# # # # # 5
왼쪽 상단 2: ↔, 오른쪽 하단 2: ↔왼쪽 상단 2: ↔, 오른쪽 하단 2: ↕왼쪽 상단 2: ↕, 오른쪽 하단 2: ↔왼쪽 상단 2: ↕, 오른쪽 하단 2: ↕

CCTV는 CCTV를 통과할 수 있다. 아래 예시를 보자.

0 0 2 0 3
0 6 0 0 0
0 0 6 6 0
0 0 0 0 0

위와 같은 경우에 2의 방향이 ↕ 3의 방향이 ←와 ↓인 경우 감시받는 영역은 다음과 같다.

# # 2 # 3
0 6 # 0 #
0 0 6 6 #
0 0 0 0 #

사무실의 크기와 상태, 그리고 CCTV의 정보가 주어졌을 때, CCTV의 방향을 적절히 정해서, 사각 지대의 최소 크기를 구하는 프로그램을 작성하시오.


 입력


첫째 줄에 사무실의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에는 사무실 각 칸의 정보가 주어진다. 0은 빈 칸, 6은 벽, 1~5는 CCTV를 나타내고, 문제에서 설명한 CCTV의 종류이다. 

CCTV의 최대 개수는 8개를 넘지 않는다.


 출력


첫째 줄에 사각 지대의 최소 크기를 출력한다.


해결 방법은 N,M 그리고 CCTV의 개수가 크지 않기 때문에 모든 CCTV 배치를 구해주고 그중 가장 작은 사각지대를 선택하면 되는 비교적 간단한 문제입니다. 

그러나 CCTV의 종류에 따라 감시하는 방향을 각각 설정해줘야 하기 때문에 코드가 상당히 길어지고 모든 CCTV 경우의 수를 구하는게 어렵게 느껴질수도 있습니다.

저도 이 모든 경우의 수를 어떻게 구할까 한참 고민하다 재귀가 가장 구현하기 편할거같아 재귀함수를 이용하여 소스를 작성하였습니다. 



 void cal(vector<CCTV> cv, int index, int state) {

if (index >= cv.size())

return;

if (state > 5)

return;

for (int i = 0; i < n; i++) {

for (int j = 0; j < m; j++) {

if (map[i][j] == 7)

map[i][j] = 0;

}

}


cv[index].state = state;

for (int i = 0; i < cv.size(); i++)

cv[i].check(map);


int temp = count(map);

rst = (rst > temp) ? temp : rst;


cal(cv, index, state + 1);

cal(cv, index + 1, 1);


}


굵게 표시한 부분이 경우의 수를 구해주는 재귀 호출인데 index는 CCTV의 종류를 뜻하고 state는 CCTV의 감시 방향을 나타냅니다.


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
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF 100000000
 
using namespace std;
int n, m, rst = 0;
int **map;
 
class CCTV {
public:
    int x, y, state, type;
    CCTV(int y, int x, int type) {
        this->x = x;
        this->y = y;
        this->type = type;    //CCTV의 종류
        this->state = 1;      //CCTV가 보는 방향 1:상,2:우,3:하,4:좌
    }
 
    void up(int **arr){
        for (int i = this->y - 1; i >= 0; i--) {
            if (arr[i][this->x] == 6)
                break;
            else if (arr[i][this->x] == 0)
                arr[i][this->x] = 7;
        }
    }
    void right(int **arr) {
        for (int i = this->x + 1; i < m; i++) {
            if (arr[this->y][i] == 6)
                break;
            else if (arr[this->y][i] == 0)
                arr[this->y][i] = 7;
        }
    }
    void down(int **arr) {
        for (int i = this->y + 1; i < n; i++) {
            if (arr[i][this->x] == 6)
                break;
            else if (arr[i][this->x] == 0)
                arr[i][this->x] = 7;
        }
    }
    void left(int **arr) {
        for (int i = this->x - 1; i >= 0; i--) {
            if (arr[this->y][i] == 6)
                break;
            else if (arr[this->y][i] == 0)
                arr[this->y][i] = 7;
        }
    }
 
    void check(int **arr) {
        switch (this->type)
        {
        case 1:
            if (this->state == 1) {
                up(arr);
            }
            else if (this->state == 2) {
                right(arr);
            }
            else if (this->state == 3) {
                down(arr);
            }
            else if (this->state == 4) {
                left(arr);
            }
            break;
        case 2:
            if (this->state == 1 || this->state == 3) {
                up(arr);
                down(arr);
            }
            else if (this->state == 2 || this->state == 4) {
                right(arr);
                left(arr);
            }
            break;
        case 3:
            if (this->state == 1) {
                up(arr);
                right(arr);
            }
            else if (this->state == 2) {
                right(arr);
                down(arr);
            }
            else if (this->state == 3) {
                down(arr);
                left(arr);
            }
            else if (this->state == 4) {
                left(arr);
                up(arr);
            }
            break;
        case 4:
            if (this->state == 1) {
                left(arr);
                up(arr);
                right(arr);
            }
            else if (this->state == 2) {
                up(arr);
                right(arr);
                down(arr);
            }
            else if (this->state == 3) {
                right(arr);
                down(arr);
                left(arr);
            }
            else if (this->state == 4) {
                down(arr);
                left(arr);
                up(arr);
            }
            break;
        case 5:
            up(arr);
            left(arr);
            down(arr);
            right(arr);
            break;
        }
    }
 
};
 
int count(int **arr) {
    int temp = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (arr[i][j] == 0)
                temp++;
        }
    }
    return temp;
}
 
void cal(vector<CCTV> cv, int index, int state) {
    
    if (index >= cv.size())
        return;
    if (state > 5)
        return;
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (map[i][j] == 7)
                map[i][j] = 0;
        }
    }
 
    cv[index].state = state;
    for (int i = 0; i < cv.size(); i++)
        cv[i].check(map);
 
    int temp = count(map);
    rst = (rst > temp) ? temp : rst;
 
    cal(cv, index, state + 1);
    cal(cv, index + 1, 1);
 
}
 
int main() {
 
    scanf("%d %d", &n, &m);
    vector<CCTV> cctv;
    map=new int*[n];
 
    for (int i = 0; i < n; i++)
        map[i] = new int[m];
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &map[i][j]);
            if (1 <= map[i][j] && map[i][j] <= 5) {
                cctv.push_back(CCTV(i, j, map[i][j]));
            }
            else if (map[i][j] == 0)
                rst++;
        }
    }
 
    cal(cctv, 0, 1);
 
    printf("%d", rst);
    return 0;
}
cs

'알고리즘 문제 > 브루트 포스' 카테고리의 다른 글

[백준] 14697번: 방 배정하기 - C++  (0) 2019.05.28
[백준] 15686번:치킨 배달 - C++  (0) 2018.07.19

문제 출처:https://www.acmicpc.net/problem/15686


 문제


크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 7, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.


 입력


첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.


 출력


첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최소값을 출력한다.



이 문제는 


1.입력으로 들어오는 집과 치킨의 좌표를 각각 다른 벡터에 넣어준다.

2.모든 치킨집에서 M개의 치킨집을 뽑는 모든 조합을 구해준다.

3.구해진 모든 조합의 '도시의 치킨 거리'를 구하고 그중 가장 작은 값을 출력해준다.


의 과정을 거쳐 해결하였습니다.


1번에서 벡터를 쓴 이유는 문제의 테스트 케이스에서 집과 치킨집이 몇개 들어오는지 확실하지 않기 때문입니다. 


2번에서 "모든 경우의 수를 구하면 너무 많은 조합이 나오지 않을까?" 하실수도 있습니다. 

하지만 문제를 읽어보면 치킨집은 1~13개 밖에 안되고 따라서 모든 경우의 수를 구해도 그 수가 적다는 것을 알 수 있습니다.

저는 재귀를 이용한 조합 알고리즘을 이용하여 모든 조합을 구해주었습니다 아래가 그 코드입니다. 



 void combination(int arr[], int index, int n, int k, int target) {          //치킨집의 모든 조합 구해주는 함수

if (k == 0) {

int temp = select(arr);

rst = (temp < rst) ? temp : rst;           //새로 구해진 치킨거리가 더 적으면 결과값을 바꿔준다

}

else if (target == n)

return;

else {

arr[index] = target;

combination(arr, index + 1, n, k - 1, target + 1);

combination(arr, index, n, k, target + 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
#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>
#define INF 100000000
 
using namespace std;
 
class COORD {            //좌표 저장하기 위한 클래스
public:
    int x, y;
    COORD(int y, int x) {
        this->x = x;
        this->y = y;
    }
};
 
int rst = INF, n, m;
vector<COORD> house, chicken;
 
int select(int arr[]) {     //구해진 조합을 가지고 집과의 거리를 비교하고 도시의 치킨 거리를 구해주는 함수
    int sum = 0;
    for (int i = 0; i < house.size(); i++) {
        int distance = INF;
        for (int j = 0; j < m; j++) {
            int temp = abs(house[i].x - chicken[arr[j]].x) + abs(house[i].y - chicken[arr[j]].y);
            distance = (temp < distance) ? temp : distance;
        }
        sum += distance;
    }
    return sum;
}
 
void combination(int arr[], int index, int n, int k, int target) {          //치킨집의 모든 조합 구해주는 함수(조합)
    if (k == 0) {
        int temp = select(arr);
        rst = (temp < rst) ? temp : rst;           //새로 구해진 치킨거리가 더 적으면 결과값을 바꿔준다
    }
    else if (target == n)
        return;
    else {
        arr[index] = target;
        combination(arr, index + 1, n, k - 1, target + 1);
        combination(arr, index, n, k, target + 1);
    }
}
 
int main() {
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int temp;
            scanf("%d", &temp);
            if (temp == 2)
                chicken.push_back(COORD(i, j));
            if (temp == 1)
                house.push_back(COORD(i, j));
        }
    }
    int *arr = new int[m];
 
    combination(arr, 0, chicken.size(), m, 0);
    
    printf("%d", rst);
 
    return 0;
}
cs


'알고리즘 문제 > 브루트 포스' 카테고리의 다른 글

[백준] 14697번: 방 배정하기 - C++  (0) 2019.05.28
[백준] 15683번: 감시 - C++  (0) 2018.07.20

+ Recent posts

티스토리툴바