접근방법

• 문제의 핵심은 두 건물 사이에서 선분을 그었을 때, 다른 건물이 있다면 볼 수 없는 상태

• 건물간에 기울기를 이용해서 관측 가능함을 체크할 수 있음

• 한 건물에서 나머지 건물로 기울기를 확인할 때, 기존 검사된 기울기들보다 기울기가 커야 관측이 가능

• 한쪽에서 관측이 가능하다면 반대쪽에서도 관측이 가능

시간복잡도

• 한 건물에서 나머지 건물들을 확인하면 되므로 시간복잡도는 O(N^2)

해설코드

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		int N = Integer.parseInt(stk.nextToken());
		int[] arr = new int[N];
		int answer = 0;
		boolean[][] chk = new boolean[N][N];
		
		stk = new StringTokenizer(br.readLine());
		for(int i = 0; i < N; i++){
			arr[i] = Integer.parseInt(stk.nextToken());
		}
		
		for(int i = 0; i < N; i++){
			long tx = 1;
			long ty = -1000000001;
			int cnt = 0;
			
			for(int j = i + 1; j < N; j++){
				long dx = j - i;
				long dy = arr[j] - arr[i];
				
				if(ty * dx < dy * tx){
					tx = dx;
					ty = dy;
					chk[i][j] = true;
					cnt++;
				}
			}	
			
			for(int j = 0; j < i; j++){
				if(chk[j][i]) cnt++;
			}
			
			answer = Math.max(answer, cnt);
		}
		
		bw.write(answer + "\n");
		bw.flush();
	}
}