10881. 프로도의 선물 포장

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

Solution

Keyword

모든 케이스를 보면서 블럭을 넣을 때 최적이 아닌 케이스로 진행되는 경우가 있어서
문제가 있다고 생각했으나 실제로 다른 경우의 수를 탐색하면서 블럭을 넣는 순서가 바뀌면 그 케이스에서 최적의 솔루션을 찾아내기 때문에 문제가 없음을 알 수 있었다.

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
int ans = 1e9;

void dfs(int i, int w, int h, vector<int> &p, vector<pii> &v)
{
    if (i == 3)
    {
        ans = min(ans, w * h);
        return;
    }
    int idx = p[i];
    for (int k = 0; k < 2; k++)
    {
        swap(v[idx].first, v[idx].second);
        int x = v[idx].first, y = v[idx].second;
        dfs(i + 1, w + x, max(h, y), p, v);
        dfs(i + 1, max(w, x), h + y, p, v);
    }
}

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while (t--)
    {
        vector<pii> v;
        for (int i = 0; i < 3; i++)
        {
            int x, y; cin >> x >> y;
            v.push_back({ x, y });
        }
        ans = 1e9;
        vector<int> p = { 0, 1, 2 };
        do {
            dfs(0, 0, 0, p, v);
        } while (next_permutation(p.begin(), p.end()));

        cout << ans << "\n";
    }
}