[BOJ 2447 / C++] 피자 굽기

문제

주어진 오븐 모양에 피자 쌓기

문제 페이지

키포인트

• 오븐에서 깊은 곳의 지름이 아무리 길어도 위쪽의 지름이 짧으면 긴 것이 의미가 없다.

  • ex. 3층 지름 = 9 인데 2층 지름 = 5 라면 어차피 지름이 5보다 크면 2층을 통과 못함.

• 추가로 피자가 들어가지 못하는 경우를 잘 생각하자.

코드

#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]

마지막으로 피자가 남았는데 오븐에 공간이 없는 경우와 마지막 피자를 넣으려고 보았더니 오븐에 공간이 없는 경우를 예외 처리한다.

느낀점

예외 처리부분에서 시간이 좀 걸렸다.

항상 풀고 나서 이런 예외나 문제 조건을 경시해서 시간을 더 쓰게되는 문제가 많네...