주어진 오븐 모양에 피자 쌓기
오븐에서 깊은 곳의 지름이 아무리 길어도 위쪽의 지름이 짧으면 긴 것이 의미가 없다.
추가로 피자가 들어가지 못하는 경우를 잘 생각하자.
#include <iostream>
#include <algorithm>
using namespace std;
int d, n, pizza, depth, res;
int oven[300001];
int main() {
cin >> d >> n;
depth = d-1;
for (int i = 0; i < d; i++) {
cin >> oven[i];
if (i > 0) {
if (oven[i] > oven[i - 1]) {
oven[i] = oven[i - 1];
}
}
}
for (int i = 0; i < n; i++) {
cin >> pizza;
if (depth < 0) { // 피자가 남아있는데 오븐에 공간이 없으면 0 출력
cout << 0 << endl;
return 0;
}
for (int j = depth; j >= 0; j--) {
if (oven[j] < pizza) { // 오븐 지름보다 피자 지름이 더 크면 피자 안 들어감
depth--;
if (j == 0) { // 오븐의 마지막공간에 마지막 피자가 들어가지 않으면 공간이 없어서 못들어 간 것
cout << 0 << endl;
return 0;
}
}
else { // 피자 들어감
//cout << pizza << " " << depth << endl;
res = depth;
depth--;
break;
}
}
}
cout << res+1 << endl;
return 0;
}
오븐의 bottom부터 피자와 비교해나간다.
피자가 만들어진 순서대로 오븐에 들어가는데 bottom부터 비교했을 때 못 쌓는다면 그 다음 피자도 못 쌓게 된다. [depth-=1]
피자가 들어갈 수 있다면 해당 공간에 다른 피자를 넣을 수는 없다. [depth-=1]
마지막으로 피자가 남았는데 오븐에 공간이 없는 경우와 마지막 피자를 넣으려고 보았더니 오븐에 공간이 없는 경우를 예외 처리한다.
예외 처리부분에서 시간이 좀 걸렸다.
항상 풀고 나서 이런 예외나 문제 조건을 경시해서 시간을 더 쓰게되는 문제가 많네...