[백준, C++] 2304 - 창고 다각형

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

2304번: 창고 다각형

 

문제 분석

N개의 막대 기둥이 일렬로 서 있는데, 이 막대 기둥들을 이용해 양철로 된 지붕을 만든단다. 근데 면적이 가장 작은 창고를 만들고 싶다고 한다. 딱히 특별한 알고리즘을 써서 풀어야 하는게 아니라 단순한 구현 문제이다. 어떻게 문제를 풀어야할까 잠깐 생각을 해봤는데, 은근 단순한 솔루션을 생각해낼 수 있었다.

구해야 할 넓이는 이런 식이다.

가장 높이가 높은 막대 기둥을 기준으로, 왼쪽 부분의 넓이 + 가장 높이가 높은 막대 기둥이 차지하는 넓이 + 오른쪽 부분의 넓이를 계산하면 된다고 판단했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Pillar {
    int leftPosition;
    int height;

    Pillar(int leftPosition, int height) {
        this->leftPosition = leftPosition;
        this->height = height;
    }
};

int n, l, h;
vector<Pillar> pillars;
int result;

bool compare(Pillar p1, Pillar p2) {
    return p1.leftPosition < p2.leftPosition;
}

void getInput() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l >> h;
        pillars.push_back(Pillar(l, h));
    }
}

void solve() {
    // 기둥의 왼쪽 면의 위치가 정렬된 상태로 입력을 받는 것이 아니므로 정렬 수행
    sort(pillars.begin(), pillars.end(), compare);
    
    // 가장 높은 기둥의 인덱스 구하기
    int highestPillarIndex = -1;
    int highestPillarHeight = -1;
    for (int i = 0; i < pillars.size(); i++) {
        Pillar pillar = pillars[i];
        if (highestPillarHeight < pillar.height) {
            highestPillarHeight = pillar.height;
            highestPillarIndex = i;
        }
    }

    // 가장 높은 기둥의 왼쪽 부분 넓이 구하기
    int lastHighestPosition = pillars[0].leftPosition;
    int lastHighestHeight = pillars[0].height;
    for (int i = 1; i <= highestPillarIndex; i++) {
        Pillar pillar = pillars[i];

        if (i == highestPillarIndex) {
            result += lastHighestHeight * (pillars[highestPillarIndex].leftPosition - lastHighestPosition);
            break;
        }

        if (pillar.height > lastHighestHeight) {
            result += lastHighestHeight * (pillar.leftPosition - lastHighestPosition);
            lastHighestPosition = pillar.leftPosition;
            lastHighestHeight = pillar.height;
        }
    }

    // 가장 높은 기둥의 넓이 구하기
    result += highestPillarHeight;

    // 가장 높은 기둥의 오른쪽 부분 넓이 구하기
    lastHighestPosition = pillars[n - 1].leftPosition + 1;
    lastHighestHeight = pillars[n - 1].height;
    for (int i = pillars.size() - 2; i >= highestPillarIndex; i--) {
        Pillar pillar = pillars[i];

        if (i == highestPillarIndex) {
            result += lastHighestHeight * (lastHighestPosition - (pillars[highestPillarIndex].leftPosition + 1));
            break;
        }

        if (pillar.height > lastHighestHeight) {
            result += lastHighestHeight * (lastHighestPosition - (pillar.leftPosition + 1));
            lastHighestPosition = pillar.leftPosition + 1;
            lastHighestHeight = pillar.height;
        }
    }
}

void printResult() {
    cout << result << "\n";
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    getInput();
    solve();
    printResult();
}

 

코드 설명

Pillar라는 구조체를 정의했다. 이 구조체의 멤버 변수는 막대 기둥의 왼쪽 면의 위치를 나타내는 leftPosition과 높이를 나타내는 height이다. 입력을 받아서 벡터에 저장한 후, 앞서 말한 것처럼 가장 높은 막대 기둥의 왼쪽 넓이 + 가장 높은 막대 기둥의 넓이 + 가장 높은 막대 기둥의 오른쪽 넓이를 계산해 답을 출력하도록 했다.

 

왼쪽 부분의 넓이를 구하는 것과 오른쪽 부분의 넓이를 구하는 것은 정반대로 생각하면 되기 때문에, 왼쪽 부분의 넓이를 구하는 방법만 설명하겠다. 가장 첫 번째 기둥을 '지금까지 있던 기둥 중 가장 높은 기둥' 이라고 정의한 후, 두 번째 기둥부터 가장 높은 기둥까지 하나씩 살펴보며 '지금까지 있던 기둥 중 가장 높았던 기둥' 보다 더 높은 기둥이 나오면 그 때의 면적을 계산하고, 이를 누적해 더해가는 방식이다. 가장 높았던 기둥이 갱신되면 당연히 가장 높았던 기둥 정보를 갱신한다.

 

오른쪽 부분의 넓이를 구하는 것은 사실 leftPosition에 +1을 해주는 방식을 사용했는데, 지금 블로그를 작성하며 생각해보니 굳이 그러지 않아도 됐을 것 같다. 어차피 모든 기둥마다 leftPosition + 1을 한 값을 사용하기 때문인데, 그럼 +1을 하나마나 두 기둥의 position 차이는 같아서이다.

 

문제 자체가 어렵지는 않았는데, 고려했어야 할 사항은 1. 기둥의 정보는 왼쪽부터 순서대로 주어지지 않아 별도의 정렬이 필요하다. / 2. 가장 높은 기둥이 전체 기둥 중 몇 번째인지 찾아야 한다. / 3. 넓이를 반복문 하나로 찾는 게 아니라 2개의 반복문(왼쪽 넓이 구하기, 오른쪽 넓이 구하기)과 가장 높은 기둥 넓이 계산을 포함해 문제를 분할해서 생각해야 했다. 정도인 것 같다.

 

잡소리) 최근에 어떤 한 회사에서 코딩 테스트를 봤는데 불합격해서 뭔가 씁쓸했다. 코딩 테스트에서 불합격한 경험이 작년에는 많지는 않았던 것으로 기억하는데, 확실히 최근 알고리즘 공부를 하지 않아서인지 실력이 좀 많이 녹슬었던 것 같다. 곧 하반기 채용을 준비해야 하니까 열심히 쭉 해야겠다.