문제 URL : https://www.acmicpc.net/problem/2539
2539번: 모자이크
수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서
www.acmicpc.net
문제접근법 : 초등부 문제인데 생각보다 어렵더군요 이걸 어떻게 붙일지 고민고민했는데
문제를 잘 읽어보니
3번조건에 모든 색종이는 반드시 도화지의 밑변에 맞추어 붙인다. 이때 색종이를 겹쳐서 붙일 수 있다.
가장 왼쪽에있는것을 먼저붙이고 그사이즈만큼 커버리면 다시 그쪽에서 붙인다고 생각해서 풀었습니다.
그러나 그사이즈가 y좌표보다 클때는 붙일수없으니 사이즈를 좀더 커야겠죠?
이분탐색을 이용해서 풀었습니다.
소스코드 :
|
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
|
//By콩순이냉장고
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int h, w, paper, n;
vector<pair<int, int>> v;
bool cmp(pair<int, int> a, pair<int, int> b) {
return a.second < b.second;
}
void input() {
cin >> h >> w >> paper >> n;
for (int i = 0; i < n; i++) {
int y, x;
cin >> y >> x;
v.push_back({ y,x });
}
}
int put(int size) {
int cnt = 1;
int left = v[0].second;//왼쪽 x좌표에서 가장 먼저붙임 그안에 붙였을때 모든걸 커버시킴
for (int i = 1; i < n; i++) {
if (v[i].first > size)//맨아래칸부터 붙여야하니 높이가 큼 애초에 불가능
return 1e8;
if (left + size - 1 < v[i].second) {
left = v[i].second;
cnt++;
}
}
return cnt;
}
void solve() {
sort(v.begin(), v.end(), cmp);
int first = 1, last = min(h, w);//최대 사이즈가 h,w중 작은놈이 최대 사각형을 붙일수있음
int res = last;
while (first <= last) {
int mid = (first + last) / 2;
if (put(mid) <= paper) {
last = mid - 1;
res = mid;
}
else {
first = mid + 1;
}
}
cout << res << "\n";
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
input();
solve();
}
|
cs |
궁금한점 혹은 모르는점 댓글은 언제나 환영입니다.
'백준' 카테고리의 다른 글
| 백준 11003 최솟값 찾기 (0) | 2021.05.27 |
|---|---|
| 백준 20166 문자열 지옥에 빠진 호석 (0) | 2021.05.25 |
| 백준 3079 입국심사 (0) | 2021.05.20 |
| 백준 16434 드래곤 앤 던전 (0) | 2021.05.20 |
| 백준 1981 배열에서 이동 (0) | 2021.05.20 |