[백준 1905번] 상자쌓기 (C++)

문제링크 : https://www.acmicpc.net/problem/1905

1905번: 상자 쌓기

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAX 987654321
#define pii pair <int, int>

struct xyz
{
    int lx, ly, lz, px, py, pz;
};

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int Lx, Ly, N;
    cin >> Lx >> Ly >> N;
    int result = 0;

    struct xyz arr[20000];

    for(int i = 0; i<N; i++)
    {
        cin >> arr[i].lx >> arr[i].ly >> arr[i].lz >> arr[i].px >> arr[i].py;
    }

    for(int i=0; i<N; i++)
    {
        arr[i].pz = 0; //겹치는 높이를 저장할 변수  
        for(int j = 0; j<i; j++) // ~i까지
        {
            if(arr[i].px < arr[j].lx + arr[j].px && arr[j].px < arr[i].lx + arr[i].px &&
            arr[i].py < arr[j].ly + arr[j].py && arr[j].py < arr[i].ly + arr[i].py)  //겹친다면
            {
                arr[i].pz = max(arr[i].pz, arr[j].pz + arr[j].lz);  //높이 저장
            }
        }
        result = max(result, arr[i].pz + arr[i].lz);  //겹치는 높이의 합과 현재 박스 높이의 합
    }

    cout << result;
    
    return 0;
}

겹치는 높이를 저장할 pz를 따로 선언해준다.

 

첫 사각형 (i)를 기준으로 그 다음 사각형(j)들이 겹치는 지를 확인하여 겹친다면 해당 값의 pz에 겹치는 높이를 저장한다.

해당 기준 사각형의 pz에 현재 pz와 앞에서 더해준 높이를 비교한후 큰 값을 저장하고, 마지막으로 여기에 현재 사각형(i)의 높이를 더해준다. 

 

이렇게 구한 값이 가장 클 경우 출력해준다.