아이디어

• 건물을 바라봤을 때의 각도가 앞의 건물을 바라봤을 때의 각도보다 작으면 그 건물은 보이지 않는다.
  • 위 그림에서 $\beta < \alpha$기 때문에 회색 건물은 보이지 않는다.
  • 각도가 (-)값이어도 마찬가지 (관찰자 쪽의 건물이 더 높을 때)
  • 에제 입력 3을 참고하면, 각도가 같아도 하나만 보이는 걸로 치는 듯 하다.
• 따라서 한 건물에 대해 다른 모든 건물의 각도를 비교하면 된다.
  • 이때 각도를 직접 쓰는 대신 기울기를 쓰자.
    • 기울기와 탄젠트의 정의를 생각하면, 각도의 탄젠트값이 기울기임을 알 수 있다.
    • 탄젠트는 $-90^\circ \sim 90^\circ$ 범위에서 $\theta_1$ < $\theta_2$면 $\tan \theta_1 < \tan \theta_2$다. (단조 증가)
    • 따라서 탄젠트의 여부는 대소 관계에 영향을 주지 않는다.
• 관찰자가 있는 건물$(i)$가 비교하는 건물 $(j)$보다 작으면 수업 시간에 풀었던 2493번 탑에서 썼던 방법을 쓰자.
  • 기울기를 구해 스택에 넣고, 이후 그보다 앞에 있으면서 더 작거나 같은 모든 기울기들을 지워서 계산에서 제외시킨다.
  • 모든 $0 \leq j < i$에 대해 루프가 끝났다면 스택에 남아있는 기울기 개수가 $i$ 왼쪽의 계산 결과다.
• $i$가 $j$보다 크면, 최댓값을 구할때처럼 현재까지의 최대 기울기와 비교한다.
  • 초기 기울기는 $-\infty$(Double.NEGATIVE_INFINITY)부터 시작한다.
  • 현재까지의 최대 기울기보다 기울기가 클 경우 갱신되고, 갱신될때마다 계산 결과에 +1 된다.
  • 작거나 같을 경우 무시한다.
  • 모든 $i < j < N$에 대해 루프가 끝났다면 +1한 횟수가 $i$ 오른쪽의 계산 결과다.
• 위와 같은 과정의 $i$-루프를 모든 건물에 대해 반복하여 계산 결과의 최댓값을 출력한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer tk = null;

    static int N;
    static int[] heights;

    static Deque<Double> stack = new ArrayDeque<>();

    public static void main(String[] args) throws Exception {
        N = Integer.parseInt(rd.readLine());
        heights = new int[N];

        tk = new StringTokenizer(rd.readLine());
        for (int i=0; i<N; i++)
            heights[i] = Integer.parseInt(tk.nextToken());

        int maxCnt = 0;
        for (int i=0; i<N; i++) {
            int cnt = 0;
            for (int j=0; j<i; j++) {
                double slope = (double)(heights[j] - heights[i]) / (i - j);
                while (!stack.isEmpty() && stack.peek() <= slope)
                    stack.poll();
                stack.offerFirst(slope);
            }
            cnt += stack.size();
            stack.clear();

            double maxSlope = Double.NEGATIVE_INFINITY;
            for (int j=i+1; j<N; j++) {
                double slope = (double)(heights[j] - heights[i]) / (j - i);
                if (slope > maxSlope) {
                    maxSlope = slope;
                    cnt++;
                }
            }
            maxCnt = Math.max(maxCnt, cnt);
        }
        System.out.println(maxCnt);
    }
}

메모리 및 시간

• 14292 KB / 132 ms

리뷰

• 수업에서 풀었던 문제가 도움이 되었다. 위아래와 좌우로 봐야한다는 점을 뺴곤 같은 문제라…
• Deque를 Stack으로 쓸 때 메소드 주의해야한다.
  • Deque의 front를 Stack의 top으로 쓴다.
  • push: offerFirst()
  • top: peek()
  • pop: poll()
• 왼쪽 건물 체크의 경우 그냥 역순으로 보면 됐었는데…