https://www.acmicpc.net/problem/1756
1756번: 피자 굽기
첫째 줄에 오븐의 깊이 D와 피자 반죽의 개수 N이 공백을 사이에 두고 주어진다. (1 ≤ D, N ≤ 300,000) 둘째 줄에는 오븐의 최상단부터 시작하여 깊이에 따른 오븐의 지름이 차례대로 주어진다. 셋
www.acmicpc.net
피자마다 오븐의 모든 지름을 탐색하는 완전 탐색의 경우 O(N*M)으로 300000의 데이터들을 탐색하면 시간 초과가 발생
이를 해결하기 위해 그리디 알고리즘을 적용하였으며, 풀이 후 검색해보니 이분탐색으로도 해결할 수 있다하여 이분탐색으로도 풀이 해봄
풀이
오븐의 너비는 이전 위치보다 현재 위치의 너비가 크다고해도 이전위치의 너비보다 큰 피자가 들어올 수 없다
ex) {3, 4, 5}의 너비를 가진 오븐의 경우

∴ {3, 3, 3}의 너비를 가진 것과 마찬가지(오븐을 내림차순으로 정리)
오븐의 너비 배열을 변경 후 풀이
그리디
- 현재 피자를 넣은 뒤, (현재 위치 - 1)의 위치부터 다음 피자의 위치를 탐색하도록 함 (O(N))
#include <iostream> using namespace std; int D, N; int oven_diameter[300001], pizza_diameter[300001]; int pizza_pos[300001]; int main() { cin >> D >> N; //이전 위치의 너비보다 큰 너비는 들어올수 없으므로 배열값을 수정 for (int i = 1; i <= D; i++) { cin >> oven_diameter[i]; if (i > 1 && oven_diameter[i] > oven_diameter[i - 1]) oven_diameter[i] = oven_diameter[i - 1]; } for (int i = 1; i <= N; i++) { cin >> pizza_diameter[i]; } int i=D; int cnt = 1; //역순으로 탐색하며 다음 피자에 대한 탐색을 하더라도 (이전 피자의 위치-1)에서 부터 탐색 for (int i = D; i > 0; i--) { if (oven_diameter[i] >= pizza_diameter[cnt]) { pizza_pos[cnt] = i; cnt++; } if (cnt > N) break; } if (cnt > N) cout << pizza_pos[N]; else cout << 0; return 0; }
이분탐색 O(log(N))
left =1 , right=pos-1 로 하고 flag를 이용해 이분탐색의 비교(pizza_diameter[i] <= oven_diameter[mid])를 한번이라도 만족하지 못한다면 pos=0 break로 했었는데 성공하지못함(이유 모름)
left=0, right=pos로 하니 해결 -> oven_diameter를 0까지 탐색하게 하여 oven_diameter[0]보다 작은것에 만족하게하여 pos=0으로 만들어버리는 방법을 사용
#include <iostream> using namespace std; int D, N; int oven_diameter[300001], pizza_diameter[300001]; int main() { cin >> D >> N; //오븐 너비 idx=0을 어떤 피자의 너비든 통과할 수 있는 값으로 설정 //이후 탐색에서 피자가 오븐에 들어갈수 없는 경우에 pizza_diameter[0]에는 만족하게 만들어 pos=0으로 만들기 위해 oven_diameter[0] = 987654321; for (int i = 1; i <= D; i++) { cin >> oven_diameter[i]; if (oven_diameter[i] > oven_diameter[i - 1]) oven_diameter[i] = oven_diameter[i - 1]; } for (int i = 1; i <= N; i++) { cin >> pizza_diameter[i]; } int pos = D+1; for (int i = 1; i <= N; i++) { int last_pizza = pizza_diameter[i - 1]; if (!pos)break; if (pizza_diameter[i] <= last_pizza) { pos--; continue; } int left = 0; int right = pos - 1; while (left <= right) { int mid = (left + right) / 2; //현재 피자 너비가 mid 위치의 오븐에 가능하다면 pos를 저장하고 가능한 위치를 계속 탐색 if (pizza_diameter[i] <= oven_diameter[mid] ) { pos = mid; left = mid + 1; } else { right = mid - 1; } } } cout << pos; return 0; }
'알고리즘' 카테고리의 다른 글
BOJ 15684 - 사다리 조작(C++) (0) | 2021.08.31 |
---|---|
BOJ 1946 - 신입 사원(C++) (0) | 2021.08.27 |
BOJ 17142 - 연구소3(C++) (0) | 2021.08.25 |
Programmers - 광고삽입(C++) (0) | 2021.08.24 |
BOJ 1405 - 미친로봇(C++) (0) | 2021.08.24 |
댓글