SWEA] 4796. 의석이의 우뚝 선 산

SWEA] 4796. 의석이의 우뚝 선 산

SWEA 3131. 100만 이하의 모든 소수(Link)
문제의 저작권은 SWEA에 있습니다

시간초과 날 것 같았지만 그래도 깡으로 구현했다가 역시나 시간초과를 맞이했던 문제..

구현하는 규칙을 찾는게 아니라, 수학적인 규칙을 찾는게 포인트

숫자를 나열하고 꼭지점(가장 높아졌다가 내려오는 부분)을 기준으로,
문제의 규칙이 깨지는 순간까지의 올라가는 횟수(UP)과 내려가는 횟수(DOWN)을 곱하면 된다.
규칙이 깨지면 다시 UP/DOWN은 0으로 초기화. 다시 규칙(우뚝 선 산)의 조건을 찾는다.
-
두번째 숫자부터 끝까지 탐색하면서,
이전의 숫자가 현재의 숫자보다 작다면 UP++
그렇지 않다면 down++
단, 구별해주기 위한 조건을 더 넣어서
down하다가 up하는 순간에서는 그 값들을 result에 연산하여 더해주기.
(즉, down이 0보다 크고, 현재값이 이전값보다 커졌을 때. 결과겂에 더해주고 UP/DOWN 초기화)
-
마지막에는 한번 더 result에 UP과 DOWN을 곱해서 더해주는데, 조건에 만족하지 않다면
어차피 0을 곱해주므로 정답에 영향을 미치지 않는다.
-

import java.util.Scanner;
 
public class d4_4796_의석이의우뚝선산 {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for(int tc=1; tc<=T; tc++) {
            int N = sc.nextInt();
            int[] arr = new int[N];
            for(int i=0; i<N; i++)
                arr[i] = sc.nextInt();
            
            int up = 0;
            int down =0;
            int result = 0;
            for(int i=1; i<N; i++) {
                if(arr[i-1]<arr[i]) {
                    if(down>0) {
                        result += down*up;
                        up=0;
                        down=0;
                    }
                    up++;
                }
                else {
                    down++;
                }
            }
            result += up*down;
            System.out.println("#"+tc+" "+result);
            
        }//end test cases
    }
}