[백준]1756번. 피자 굽기

[문제]

 

www.acmicpc.net/problem/1756

1756번: 피자 굽기

[풀이]

 

오븐의 지름, 피자 반죽의 지름이 주어지고 마지막 피자 반죽의 위치를 출력하면 된다.

 

처음에는 완전 탐색으로 풀까 생각했는데 N,D의 최댓 값이 300,00이라서 시간초과가 나오게 된다.

따라서  dp 방법을 사용해 구현했다.

 

depth 라는 배열에 해당 깊이에 구워질 수 있는 피자 지름의 최댓값을 저장했다.

문제 예제로 보면 

 

7 3

5 6 4 3 6 2 3

3 2 5

 

depth 배열의 값은 5 5 4 3 3 2 2 가 된다.

 

이제 오븐의 뒤에서부터 피자를 구울 수 있는 곳을 찾아가면 된다.

 

3 2 5 로 보면 지름이 3인 피자는 뒤에서 3번째의 위치에서 ( 5 5 4 3 3 2 2 ) 구울 수 있다. 

그 다음으로 지름이 2인 피자는 뒤에서 3번째보다 더 앞 부분에서 구워야 하므로 

뒤에서 4번째 위치에서 ( 5 5 4 3 3 2 2 )  구울 수 있다.

마지막으로 지름이 5인 피자는 앞에서 2번째의 위치에서 ( 5 5 4 3 3 2 2 ) 구울 수 있다.

 

이런식으로 모든 피자에 대해 반복하고 오븐의 마지막 위치를 출력하면 된다.

 

 

[코드]

 

시간 : 264ms

 

#include <iostream>
#include <vector>

#define MAX 300001

using namespace std;

int D,N;
int depth[MAX]={0,};
int pizza[MAX]={0,};

int main(void)
{
    cin >> D >> N;
    for(int i=0;i<D;i++){
        cin >> depth[i];
        if( i>0 &&  depth[i-1] < depth[i])   depth[i] = depth[i-1];
    }
    
    for(int i=0;i<N;i++)    cin >> pizza[i];
    
    int idx = 0;
    for(int i=D-1 ; i>=0; i--){
        if(depth[i] >= pizza[idx])  idx++;
        if(idx==N){
            cout << i+1;
            break;
        }
        if(i==0){
            cout <<"0";
            break;
        }
    }
    return 0;
    
}