[BOJ/백준][Gold5] 1756 : 피자 굽기 (C++)

https://www.acmicpc.net/problem/1756

1756번: 피자 굽기

 

 

[난이도] Gold5
[유형] 구현

[풀이]
오븐의 지름이 넓을 수록 피자를 넣기에 유리하지만 오븐 아래층의 지름이 아무리 넓어도
윗 층의 지름이 더 좁다면 윗 층 지름중 가장 좁은 지름만큼의 넓이를 가진 피자밖에 담을 수가 없습니다.
이를 이용해 O(N) 시간에 문제를 해결할 수 있습니다.

a 배열을 선언하여 다음과 같이 정의합니다.
a[i] : 1~i 층까지의 지름 중 가장 좁은 지름

점화식은 다음과 같습니다. 일종의 메모제이션입니다.
a[i] = min(i번 층의 지름,a[i-1])

이런 식으로 저장하게 되면 a 배열은 내림차순 형태를 띄게 됩니다.

이제 피자를 순서로 입력받으면서
D층부터 넣을 수 있는 곳에 차례대로 채워가면 됩니다.
모든 피자를 넣을 수 없는 경우 0을 출력해야 하는 것을 주의해야 합니다.

 

#include <cstdio>
#include <algorithm>
using namespace std;
int D,N,a[300001];
int main(){
    scanf("%d%d",&D,&N);
    for(int i=0;i<=D;i++) a[i]=2e9;
    for(int i=1;i<=D;i++) {
        int v;
        scanf("%d",&v);
        a[i] = min(v,a[i-1]);
    }
    int cur=D, ans=0;
    while(N--){
        int v;
        scanf("%d",&v);
        for(;cur>=0;cur--){
            if(v<=a[cur]){
                ans=cur;
                cur--;
                break;
            }    
        }
    }
    printf("%d",ans);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/1756.cpp