문제
백준 BOJ
https://www.acmicpc.net/problem/1027
1027번: 고층 건물
세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)
www.acmicpc.net
알고리즘
Brute force
풀이
각 건물에 대해 보이는 건물의 개수를 일일이 확인해본다.
건물 쌍 (l,r) (l<r)에 대해 (l,r)이 서로 볼 수 있으려면 l<k<r 인 모든 건물 k에 대해 (l~k의 기울기) < (k~r의 기울기)를 만족해야 한다.
즉
(a[k]-a[l])/(k-l) < (a[r]-a[k])/(r-k)
를 만족해야 한다.
n=50이므로 3중 for문도 거뜬하다.
728x90
'PS > BOJ' 카테고리의 다른 글
| 백준 BOJ 5582 공통 부분 문자열 (0) | 2021.06.08 |
|---|---|
| 백준 BOJ 20003 거스름돈이 싫어요 (0) | 2021.06.07 |
| 백준 BOJ 1812 사탕 (0) | 2021.06.03 |
| 백준 BOJ 17094 Serious Problem (0) | 2021.06.02 |
| 백준 BOJ 10422 (0) | 2021.05.25 |