[백준 1756] 피자 굽기

백준 1756번 : 피자 굽기

www.acmicpc.net/problem/1756

1756번: 피자 굽기

 

---

/* 문제 설명 */

N개의 피자 반죽을 오븐에다가 넣으려고 한다.

오븐은 깊은 관처럼 되어 있어서 피자를 넣으면 오븐의 밑 바닥부터 쌓이게 된다. 

이 때, 아래 그림과 같이 관의 지름은 깊이에 따라 다르다.

 

 

관의 지름과 피자의 지름이 주어졌을 때, 맨 위의 피자가 얼마나 깊이 들어가 있는지를 구하시오.

 

 

/* 해결 방안 */

예제가 다음과 같을 때, 피자를 넣으면 답은 2가 나온다.

7 3

5 6 4 3 6 2 3

3 2 5

 

>> 2

 

 

첫 번째 피자인 지름 3짜리를 오븐에 넣으면,6번째 관이 2이므로 5번째 관에 들어가게 된다.

위와 같이 배열의 처음부터 시작해서 끝까지 가는 도중에, 현재 피자보다 지름이 작은 관을 만나게 되면 그 곳에 안착하게 된다.

따라서 5 6 4 3 6 2 3 에서 마지막 관이 3이라 한들, 자신의 위에 있는 지름 2짜리의 관에 막혀버리게 되는 것이다.

 

즉, 배열이 5 6 4 3 6 2 3 이렇게 있지만, 

배열의 각 요소들은 자신보다 위(왼쪽)에 있는 관의 지름에 영향을 받으므로,

5 5 4 3 3 2 2 와 같이 동작한다.

 

만약 위와 같은 처리를 해주지 않는다면, 아래와 같은 케이스를 통과하지 못한다.

10 3
4 153 3 34 5 1615 4656 56 4 5
1 3 4

 

피자는 밑 바닥부터 들어가게 되므로,

배열의 끝에서부터 처음을 향해 반복문을 돌면서 피자를 넣어본다.

 

/* 구현 과정 */

1. 배열의 처음부터 마지막까지 돌면서 '5 6 4 3 6 2 3 → 5 5 4 3 3 2 2' 와 같이 내림차순으로 만들어준다.

2. 배열의 마지막에서 처음을 향해 for문을 돌면서 지금 보고 있는 위치에 피자를 넣을 수 있는지를 확인하면서 처리를 해준다.

 

/* 소스 코드 */

스택 느낌을 강조하고 싶어서 스택을 썼지만,

스택을 안쓰고 반복문의 끝부터 돌려주면 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX 300005
#define INF 1e9+10

int n, d, arr[MAX], pizza[MAX], ans, minn = INF;
stack<int>s;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> d >> n;
	for (int i = 0; i < d; i++) {
		cin >> arr[i];
		
		if (minn > arr[i]) minn = arr[i];
		else arr[i] = minn;
	}
	for (int i = 0; i < n; i++) cin >> pizza[i];

	for (int i = 0; i < d; i++)
	{
		if (pizza[0] > arr[i]) break;
		s.push(arr[i]);
	}

	int now = 0;
	while (!s.empty() && now < n) {
		if (s.top() >= pizza[now]) {
			ans = s.size(); now++;
		}
		s.pop();
	}

	if (now == n) cout << ans;
	else cout << 0;
}

 

/* 얻어갈 점 */

맛있는 피자를 먹고 싶습니다.

피자 맛있는 피자

 

 

 

 

---