4796. 의석이의 우뚝 선 산 (D4)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWS2h6AKBCoDFAVT&categoryId=AWS2h6AKBCoDFAVT&categoryType=CODE

이 문제는 산의 높이를 순서대로 저장한 배열에서 극대값을 찾는 문제이다.

산의 높이는 10^9까지 가지만 산의 개수가 50,000개 이하이므로 long long을 사용하지 않았다.

(산의 높이를 더하는 문제였으면 long long을 사용해야 한다.)

기본적인 아이디어부터 살펴보자.

극대값이 있고 그 주변을 감쌀 수 있는 범위의 개수를 찾는 문제이다.

순서대로 증가한 값이 극대값 앞에 2개 있고 순서대로 감소한 값이 극대값 뒤에 2개가 있다면 극대값 주변을 감싸는 범위의 개수는 2 * 2 = 4개이다.

앞에서부터 탐색하면서 상황을 살필 때 나올 수 있는 경우의 수를 찾았다.

1. 내려가다가 올라가는 경우

2. 올라가다가 내려가는 경우

3. 내려가다가 내려가는 경우

4. 올라가다가 올라가는 경우

5. 올라가지도 내려가지도 않다가 이동하는 경우

탐색 도중 나올 수 있는 경우의 수는 위 5가지이다.

(올라간다 -> 값이 그 전의 값보다 큰 경우)

(내려간다 -> 값이 그 전의 값보다 작은 경우)

올라가고 있다, 내려가고 있다는 별도의 boolean 값을 두어 처리한다.

극대값 앞의 순서대로 증가한 값의 개수는 small_front, 극대값 뒤의 순서대로 감소한 값의 개수는 small_end로 한다.

먼저, 5의 경우는 탐색이 시작됨을 의미한다. 탐색은 0번이 아닌 1번부터 시작한다. (이전 값과 비교해야 하므로)

시작 부분의 값이 증가한다면 front_flag를 true로 하여 올라가고 있음을 나타내고 small_front 카운트를 증가시킨다.

반대로 시작부분이 감소한다면 이는 극대값이 나올 수 없음을 의미한다. 따라서 end_flag만 true로 하고 카운트의 값은 변화시키지 않는다.

다음으로 3,4의 경우는 상태가 지속되고 있음을 의미한다. 따라서 flag에 따라서 해당 count만 늘려준다.

1,2의 경우가 중요하다. 2의 경우는 올라가다 내려간다. 즉, 극값을 만났음을 의미한다. 그렇기 때문에 flag 값을 2가지 모두 바꿔주고 small_end의 카운트를 증가시켜주기 시작해야 한다.

다음으로 1의 경우는 내려가다 올라가는 경우이다. 즉, 극값을 만나고 내려오다가 올라간다. 이는 우리가 찾고자 하는 범위가 끝났음을 의미한다. 그러므로 그동안 저장된 small_count와 small_end를 곱해서 result에 더해주고 0으로 초기화한다. 물론 flag도 2가지 모두 바꿔준다.

이렇게 탐색이 끝난다면 result가 구해진다. 하지만, 이 때 나올 수 있는 1가지 경우가 더 있다.

바로 극값을 만나고 내려오던 도중 끝에 도달한 경우이다. 따라서 flag를 확인하여 언급한 경우가 맞다면 result에 small_count와 small_end를 곱한 값을 더해준다.

---

- 소스 코드 -

#include <iostream>
 
int main()
{
  int T;
  scanf("%d",&T);
  
  for(int test_case=1;test_case<=T;test_case++){
    int result=0;
    int n;
    scanf("%d",&n);
    
    int arr[50001]={0};
    int small_front=0;
    int small_end=0;
    bool front_flag=false;
    bool end_flag=false;
    for(int i=0;i<n;i++){
        scanf("%d",&arr[i]);
    }
    
    for(int i=1;i<n;i++){
        if(arr[i-1]<arr[i]){
            if(!end_flag&&!front_flag){
                small_front++;
                front_flag=true;
            }else if(!end_flag&&front_flag){
                small_front++;
            }else if(end_flag&&!front_flag){
                result+=small_front*small_end;
                front_flag=true;
                end_flag=false;
                small_front=1;
                small_end=0;
            }
        }else{
            if(!end_flag&&!front_flag){
                end_flag=true;
            }else if(!end_flag&&front_flag){
                small_end++;
                front_flag=false;
                end_flag=true;
            }else if(end_flag&&!front_flag){
                small_end++;
            }
        }
    }
    if(end_flag&&!front_flag){
        result+=small_front*small_end;
    }
    printf("#%d %d\n",test_case,result);
  }
}
 

---