BOJ 1756, 피자 굽기
ProblemSolving ·이 문제는 구현 문제입니다.
풀이
피자를 도우를 위에서부터 아래로 내려서 테트리스같이 쌓아올린다고 생각하시면 좋을 것 같습니다.
예제의 오븐이
5
6
4
3
6
2
3 의 모양을 가지고 있습니다.
만약 3이라는 도우를 우리가 가지고 있다면 맨 밑에 너비가 3이어도 2의 너비의 층을 통과하지 못하기 때문에
3이란 숫자는 의미가 없습니다. 오히려 구현을 할 때 더 힘이 듭니다.
그래서 맨위에서부터 아래로 점점 내려오면서 최솟값을 그 층에 저장을 해주면 구현하기에 더 용이합니다.
5
5
4
3
3
2
2 이 되겠죠?
30만이라는 범위를 가지고 있기 때문에 이중포문을 돌리면 시간초과가 나게 됩니다.
맨 밑이 제일 작은 너비이고 밑에서부터 쌓아올라가는 것이기때문에 맨 밑의 층부터 한 포문으로 해결할 수 있습니다.
최솟값을 층에 저장하는 과정을 해주었기때문에 가능합니다.
층의 너비가 도우보다 크거나 같아질 때 (바로 밑에 층은 도우보다 작겠죠?) 그 층에 도우를 쌓습니다.
마지막에 도우를 쌓으면 그 층 (i)를 출력하고 프로그램을 종료하고 마지막 도우를 쌓지 못한다면 0을 출력해줍니다.
#include<iostream>
#include<stdio.h>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
int n, m, depth[300001],dow[300001];
int main()
{
scanf("%d %d", &n, &m);
depth[0] = 1e9;
for (int i = 1; i <= n; i++)
{
int wid;
scanf("%d", &wid);
depth[i] = min(wid, depth[i - 1]);
}
for (int j = 1; j <= m; j++)
scanf("%d", &dow[j]);
for (int j = 1, i = n; i >= 1; i--)
{
if (dow[j] <= depth[i])
j++;
if (j > m)
{
printf("%d", i);
return 0;
}
}
printf("0");
return 0;
}