Algorithm/Acmicpc
1027 고층 건물 [JAVA]
문제 분석https://www.acmicpc.net/problem/1027N개의 원소가 주어진다.각 원소는 빌딩의 높이를 의미한다.i번째 빌딩에서 j번째 빌딩이 보인다는 뜻은 두 빌딩의 꼭대기를 포함하는 직선에 그 사이의 다른 빌딩이 접하거나 만나지 않아야 한다는 것이다.이때, 가장 많은 빌딩이 보이는 빌딩에서 볼 수 있는 빌딩의 수를 구해야 한다. 처음에는, 전체 배열 중 가장 높이가 높은 값을 기준으로 LIS를 왼쪽에서 TOP 오른쪽에서 TOP해서 두번 구하는 방식으로 풀어보려 했으나.. 문제의 조건이 단순히 높이가 낮으면 보이는 것이 아닌 두 빌딩을 이은 선분에 맞닿는 빌딩이 없어야 보인다는 것이었기에 LIS로는 해당 조건을 만족시키기 꽤 어려웠다. 근데, N 자체가 50밖에 되지 않는다. 즉, n..
