알고스팟 알고리즘: 울타리 잘라내기(FENCE) [C++]

문제 출처: https://algospot.com/judge/problem/read/FENCE

algospot.com :: FENCE

1. 코드

#include <iostream>
#include <vector>

using namespace std;

int main(void)
{
    int C;
    cin >> C;

    while (C--)
    {
        int N;
        cin >> N;                       //펜스 갯수 입력

        vector<int> fence;
        for (int i = 0; i < N; i++)     //펜스 크기 입력
        {
            int temp;
            cin >> temp;
            fence.push_back(temp);
        }

        int result = 0;                 //결과값
        for (int i = 0; i < N; i++)     //모든 펜스 탐색
        {
            int right = 0, left = 0;            //right: 오른쪽에 위치한 펜스의 크기가 크거나 같다면 증가
                                                //left: 왼쪽에 위치한 펜스의 크기가 크거나 같다면 증가
            for (int j = i + 1; j < N; j++)     //오른쪽의 펜스 크기 탐색
            {
                if (fence[i] <= fence[j])
                    right++;
                else
                    break;
            }
            for (int j = i - 1; j >= 0; j--)    //왼쪽의 펜스 크기 탐색
            {
                if (fence[i] <= fence[j])
                    left++;
                else
                    break;
            }
            int tempResult = fence[i] * (left + right + 1); //현재 펜스 기준 결과값 저장
            if (tempResult > result)                        //크기가 크다면 결과값으로 저장
                result = tempResult;
        }
        cout << result << endl;
    }
    return 0;
}

(실행)

2. 풀이

아마 문제에 의도는 분할 정복을 이용하여 문제를 해결하는 것이겠지만 분할 정복하는 알고리즘이 전혀 생각이 안 나서 모든 경우를 탐색하는 방법을 활용하여 해결하였다.

int N;
cin >> N;                       //펜스 갯수 입력

vector<int> fence;
for (int i = 0; i < N; i++)     //펜스 크기 입력
{
    int temp;
    cin >> temp;
    fence.push_back(temp);
}

우선 펜스의 개수를 입력하고 vector를 이용하여 쉽게 펜스의 크기를 저장해준다.

int result = 0;                 //결과값
for (int i = 0; i < N; i++)     //모든 펜스 탐색
{
    int right = 0, left = 0;            //right: 오른쪽에 위치한 펜스의 크기가 크거나 같다면 증가
                                        //left: 왼쪽에 위치한 펜스의 크기가 크거나 같다면 증가
    for (int j = i + 1; j < N; j++)     //오른쪽의 펜스 크기 탐색
    {
        if (fence[i] <= fence[j])
            right++;
        else
            break;
    }
    for (int j = i - 1; j >= 0; j--)    //왼쪽의 펜스 크기 탐색
    {
        if (fence[i] <= fence[j])
            left++;
        else
            break;
    }
    int tempResult = fence[i] * (left + right + 1); //현재 펜스 기준 결과값 저장
        if (tempResult > result)                        //크기가 크다면 결과값으로 저장
            result = tempResult;
}

결과 값을 저장하기 위해 result 선언해주는데 다른 테스트 케이스도 입력해야 하기에 0으로 초기화를 해주고 제일 왼쪽에 위치한 펜스부터 기준으로 오른쪽에 위치한 펜스와 왼쪽에 위치한 펜스의 크기를 비교하여 기준이 되는 펜스의 크기보다 크거나 같은 펜스의 수를 측정하여 직사각형이 될 수 있는 최대의 크기를 구한다.

그리고 그 직사각형의 크기가 결괏값(result) 보다 크다면 result에 초기화를 해주고 이 과정을 반복하여 마지막 펜스까지 진행한 뒤 결괏값을 출력해준다.

3. 느낀 점

처음 이 문제의 해결 방법을 재귀를 이용하여 구현했지만 런타임 오류가 발생하여 처음에는 다른 곳에서 실수를 한 줄 알았지만 알고 보니 펜스의 수가 20000개 이하였기에 스택 오버플로우가 발생하여 사이트에서는 런타임 오류라고 발생한 것이었다. 재귀를 사용하지 않아서 코드가 많이 지저분해 보이지만 이 방법 말고는 떠올릴 수 없었다.