[백준 1027번] 고층 건물

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

 

 

 

해당 문제는 굉장히 많이 보이는 문제일 것이다. 기울기를 활용하는 문제인데, 문제를 보고 기울기를 판별해야겠다고 생각했지만 왼쪽으로 탐색했을 때와 오른쪽으로 탐색했을 때에 대해 생각을 깊게 하지 못했다.

 

요즘 내가 집중력이 산만해진 탓도 있는 것 같다,, 정신차리자.

 

 

그림과 같이 봤을 때 

• 기울기가 감소할 때에는 기울기가 작을수록
• 기울기가 증가할 때에는 기울기가 클수록

건물의 위치가 보이는 것을 알 수 있다.

 

import java.io.*;
import java.util.*;

public class BOJ_G4_1027_고층건물 {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] height = new int[N];
		int max = 0;

		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}

		// 이전 기울기보다 작아지면
		for (int i = 0; i < N; i++) {
			double curve = -Integer.MAX_VALUE;

			for (int j = i - 1; j >= 0; j--) {
				double tmp = (arr[i] - arr[j]) / (j - i);

				if (tmp > curve) {
					height[i]++;
				}
				curve = tmp;
			}

			curve = -Integer.MAX_VALUE;

			for (int j = i + 1; j < N; j++) {
				double tmp = (arr[j] - arr[i]) / (j - i);

				if (tmp > curve) {
					height[i]++;
				}
				curve = tmp;
			}

			if (height[i] > max) {
				max = height[i];
			}

		}

		System.out.println(max);
	}
}