[ 백준 ] 1756 / 피자 굽기

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
51/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1756 / 피자 굽기
 *
 * Kind :: Simulation
 *
 * Insight
 * - 오븐의 지름이 차례대로 주어지는데
 *   현재 층의 지름이 아무리 크더라도
 *   윗층의 지름이 작다면
 *   들어오는 피자의 크기는 윗층의 지름 이하일 수밖에 없다
 *   + 즉, 오븐의 지름이 윗층에서부터
 *     5 6 4 3 6 2 3
 *     이라면 결국 들어올 수 있는 피자 지름의 크기는
 *     5 5 4 3 3 2 2
 *     일 수밖에 없다
 *     # 오븐의 아래층부터 피자를 차곡차곡 넣어서
 *       모든 피자가 들어가는지 확인해주자!
 *
 * Point
 * - 피자가 모두 오븐에 들어가지 않으면
 *   0 을 출력한다는 점을 주의하자
 *   + 처음에는 들어간 피자들 중
 *     마지막 피자 반죽의 위치를 출력하는 것으로 이해했다 ㅠㅠ
 *     # 문제좀 꼼꼼히 읽자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int D, N;
    cin >> D >> N;
    int OR[D], PR[N];
    for (int i=0; i<D; i++)
        cin >> OR[i];
    for (int i=0; i<N; i++)
        cin >> PR[i];

    // Process
    /* 오븐의 지름 갱신
     * 현재층의 지름 = min(윗층의 지름, 현재층의 지름) */
    for (int i=1; i<D; i++) {
        OR[i] = min(OR[i], OR[i-1]);
    }

    int idx = 0; /* 피자 반죽 인덱스 */
    int ans = -1; /* 마지막 피자 반죽의 위치 */
    for (int i=D-1; i>=0 && idx<N; i--) {
        if (OR[i] >= PR[idx]) { /* 현재 층에 피자 반죽을 놓을 수 있다면 */
            ans = i+1; /* 위치 기록 */
            idx++; /* 피자 반죽 인덱스 증가 */
        }
    }

    /* 모든 피자를 넣지 못했다면 */
    if (idx != N) {
        ans = 0;
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글