백준 1047: 울타리 [C/C++]

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

1047번: 울타리

 

코드

 

#include <iostream>
#include <algorithm>
#include <vector>
static const auto fastio = []() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    return 0;
}();
using namespace std;
typedef struct Tree {
    int y, x, v, n;
} tree;
bool cmp1 (tree a, tree b) {
    if (b.v < a.v) return true;
    else return false;
}
bool cmp2 (tree a, tree b) {
    if (a.y < b.y) return true;
    else return false;
}
bool cmp3 (tree a, tree b) {
    if (a.x < b.x) return true;
    else return false;
}
int n, res = 100000;
vector<tree> fence, yfence, xfence;
vector<bool> repeated;
int main() { 
    cin >> n;
    fence = vector<tree>(n);
    xfence = vector<tree>(n);
    yfence = vector<tree>(n);
    for (int i = 0; i < n; i++) cin >> fence[i].y >> fence[i].x >> fence[i].v;
    sort(fence.begin(), fence.end(), cmp1);
    for (int i = 0; i < n; i++) fence[i].n = i;
    for (int i = 0; i < n; i++) yfence[i] = xfence[i] = fence[i];
    sort(yfence.begin(), yfence.end(), cmp2);
    sort(xfence.begin(), xfence.end(), cmp3);
    for (int right = n - 1; right >= 0; right--) {
        for (int left = 0; left <= right; left++) {
            for (int high = n - 1; high >= 0; high--) {
                for (int low = 0; low <= high; low++) {
                    
                    int length = 0, cnt = 0;
                    repeated = vector<bool>(n);
                    for (int i = right + 1; i < n; i++) repeated[yfence[i].n] = true;
                    for (int i = left - 1; i >= 0; i--) repeated[yfence[i].n] = true;
                    for (int i = high + 1; i < n; i++) repeated[xfence[i].n] = true;
                    for (int i = low - 1; i >= 0; i--) repeated[xfence[i].n] = true;
                    
                    for (int i = 0; i < n; i++) {
                        if (repeated[i]) {
                            length += fence[i].v;
                            cnt++;
                        }
                    }
                    int fenceLength = ((yfence[right].y - yfence[left].y) + (xfence[high].x - xfence[low].x)) * 2;
                    for (int i = 0; i < n; i++) {
                        if (fenceLength <= length) break;
                        if (repeated[i]) continue;
                        length += fence[i].v;
                        cnt++;
                    }
                    if (fenceLength <= length) res = min(res, cnt);
                }
            }
        }
    }
    cout << res;
    return 0;
}
 

풀이

전제:

나무는 좌표, 길이, 길이의 순서를 나타내는 구조체로 표현합니다.

길이의 순서로, y좌표로, x좌표로 정렬한 구조체 벡터가 있습니다.

y좌표로, x좌표로 정렬한 구조체 벡터는 울타리의 개형을 정하기 위하여 필요합니다.

울타리의 개형이 정해졌을 때, 길이의 순서대로 우선적으로 자르기 위하여 길이의 순서대로 정렬한 벡터가 필요합니다.

 

1.  모든 울타리의 길이를 표현합니다.

울타리는 잘리지 않은 최우측, 좌측, 상단, 하단 나무로 길이가 정해지므로 4차원 반복문을 이용해 모든 경우의 수를 표현합니다.

 

2.  잘려진 나무의 길이를 구하고, 이를 활용하여 잘라야 하는 나무의 최소 개수를 구합니다.

울타리 밖에 있는 나무의 길이의 합을 구합니다.

이 값이 울타리의 길이보다 작은 경우 울타리 안에 있는 나무를 잘라 더해줍니다.

총 잘린 나무의 수의 최소 값을 구하여 출력합니다.