[ SWEA 4796 ] 의석이의 우뚝 선 산 (C++)

SWExpertAcademy의 의석이의 우뚝 선 산(4796 / D4) 문제이다.

[ 문제풀이 ]

1) 먼저, 우뚝 선 산이 될 수 있는 구간의 갯수를 어떻게 찾아내는지 부터 알아보자.

   예를 들어서 다음과 같은 상황이라고 생각해보자.

   [ 1 , 3 , 5 , 4 , 2 ]

   이 경우, [ 1 3 5 4 ] , [ 1 3 5 4 2 ] , [ 3 5 4 ] [ 3 5 4 2 ] 로 총 4개의 구간이 존재한다.

   그럼 '4'라는 값을 식으로 한번 도출해보자.

   1 → 3 으로 갈 때, 산의 높이가 '1번' 증가하였다.

   3 → 5 로 갈 때, 산의 높이가 '2번' 증가하였다.

   5 → 4 로 갈 때, 산의 높이가 '1'번 감소하였다.

   4 → 2 로 갈 때, 산의 높이가 '2'번 감소하였다.

   즉, "해당 구간에서 산의 높이가 증가하는 구간의 갯수 x 산의 높이가 감소하는 구간의 갯수" 로 우뚝 선 산이 될 수

   있는 구간의 갯수를 구할 수 있다.

   한번 저 식이 올바른지 확인해보자.

   [ 1 , 4 , 7 , 8 , 5 , 3 , 6 , 9 ] 이 경우를 확인해보자.

   먼저, 이 구간에서 산의 높이가 증가하는 횟수를 한번 Count해보자.

   [ 1 4 ] [ 4 7 ] [7 8 ] [ 3 6 ] [ 6 9 ] 로 총 5개의 증가하는 구간이 있다.

   [ 8 5 ] [ 5 3 ] 으로 총 2개의 감소하는 구간이 있다.

   그럼 5 x 2 = 10 으로 총 10개의 구간이 존재해야 할 것이다.

   하지만 직접 구간을 만들어보자.

   [ 1 4 7 8 5 ] [ 1 4 7 8 5 3 ] [ 4 7 8 5 ] [ 4 7 8 5 3 ] [ 7 8 5 ] [ 7 8 5 3 ]

   이렇게 구간이 6개 밖에 나오지 않는다.

   위에서 말한 식을 대입했을 때의 결과와 차이가 나는 이유는 뒤에서 증가하는 부분인 [ 3 6 ] [ 6 9 ] 는 사실 상,

   우뚝 선 산의 구간을 카운트 하는데 아무런 영향을 미치지 못하기 때문이다.

   즉 ! 산의 높이가 증가하는 구간 → 산의 높이가 감소하는 구간 → 산의 높이가 증가하는 구간

   이렇게 발생할 경우, 그 전에 산의 높이가 감소하는 구간에서 한번 끊어줘야 한다.

   그럼 다시한번 해보자.

   산의 높이가 증가하는 구간 = [ 1 4 ] [ 4 7 ] [ 7 8 ] 로 총 3구간.

   산의 높이가 감소하는 구간 = [ 8 5 ] [ 5 3 ] 으로 총 2구간.

   따라서, 구간의 총 갯수는 3 x 2 = 6 으로 6구간이 나오게 된다.

  

   또 한가지 상황을 더 생각해보자.

   [ 5 3 1 2 4 ] 가 있다면 ?? 딱 봐도 우뚝 선 산이 될 수 있는 구간의 갯수는 0개이다.

   하지만, 위의 공식대로 감소하는 구간 = 2개, 증가하는 구간 = 2개 → 총 4개의 구간 존재 ! 라고 해버리면 안된다.

   "감소하는 구간을 Count하기 전에, 증가하는 구간이 이전에 존재했는지를 고려" 해줘야 한다.

   위의 상황 같은 경우 5 → 3으로 갈 때, 이 전에 증가하는 구간이 존재하지 않았다. 따라서, 카운트를 해주면 안된다.

   마지막으로 정리하고 소스코드로 확인해보자.

"증가하는 구간의 갯수 x 감소하는 구간의 갯수" 로, 우뚝 선 산이 될 수 있는 구간의 갯수를 구할 수 있음.

하지만 ! 반드시 그 형태가, " 증가하는 구간 → 감소하는 구간 " 의 형태로 이루어져 있어야 하며,

그 이후에 등장하는 "증가하는 구간"은 위와 같은 방식으로 또 다른 계산을 진행해 주어야 한다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 50010
typedef long long ll;
using namespace std;
 
int N;
int Arr[MAX];
ll Answer;
 
void Initialize()
{
    Answer = 0;
}
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++) cin >> Arr[i];
}
 
void Solution()
{
    int Increase, Decrease;
    Increase = Decrease = 0;
    /* Increase = 증가하는 구간의 갯수 */
    /* Decrease = 감소하는 구간의 갯수 */
 
    for (int i = 0; i < N - 1; i++)
    {
        int Prev = Arr[i];
        int Next = Arr[i + 1];
        
        if (Prev < Next) // 증가하는 구간일 때
        {
            /* 증가하는구간 -> 감소하는 구간의 형태로 존재해야 하므로 
             * 증가하는 구간이 나왔을 때, 기존에 존재하는 감소하는 구간의 갯수는 0개여야함.
             * 0이 아니라면, 새로운 구간이 나왔다는 말이므로, 계산을 끝내고 구간의 갯수를 초기화.
             */
            if (Decrease == 0) Increase++;
            else
            {
                Answer = Answer + (Increase * Decrease);
                Increase = 1;
                Decrease = 0;
            }
        }
        else
        {
            /* 감소하는 구간일 경우, 기존에 증가하는 구간이 존재했는지 고려. */
            if (Increase != 0) Decrease++;        
        }
    }
    Answer = Answer + (Increase * Decrease);
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}