백준 1027번 고층 건물

정보

문제 바로가기 [클릭]

난이도: Gold4

관련 개념: #수학 #브루트포스 알고리즘 #기하학

---

조건

시간 제한	메모리 제한
2초	128 MB

---

문제

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.

---

입력

첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.

---

출력

첫째 줄에 문제의 정답을 출력한다.

---

예제 입출력 1

입력

15
1 5 3 2 6 3 2 6 4 2 5 7 3 1 5

출력

7

---

예제 입출력 2

입력

1
10

출력

0

---

예제 입출력 3

입력

4
5 5 5 5

출력

2

---

예제 입출력 4

입력

5
1 2 7 3 2

출력

4

---

예제 입출력 5

입력

10
1000000000 999999999 999999998 999999997 999999996 1 2 3 4 5

출력

6

---

코드(파이썬)

n = int(input())
buildings = list(map(int, input().split()))
link = {i:list() for i in range(n)}

for i in range(n):
    g = -1000000000
    highest = 1000000001
    
    for j in range(i+1, n):
        now_g = (buildings[j]-buildings[i]) / (j-i)
        line = g * (j-i) + buildings[i]
        
        if buildings[j] > line:
            g = now_g
            link[i].append(j)
            link[j].append(i)
            highest = buildings[j]
        elif g < now_g < 0 and highest > line:
            g = now_g
            link[i].append(j)
            link[j].append(i)
        
print(max([len(v) for v in link.values()]))

---

특이사항

• 각 지점에서 오른쪽에 있는 모든 지점을 확인하는 단순한 방식
• 내 코드(30,840KB, 68ms)에 비해 우수한 코드(바로가기, 30,840KB, 68ms)와 비교

  • N=int(input(""))
    numL=list(map(int,input("").split()))
    height_L=[0]*N
    for i in range(N-1):
        max_angle=0
        for j in range(i+1,N):
            angle=(numL[j]-numL[i])/(j-i)
            if j==i+1 or angle>max_angle:
                max_angle=angle
                height_L[i]+=1
                height_L[j]+=1
    print(max(height_L))
    
    

  • 최고 높이 확인
    • 기존: link에 각 요소를 저장하고 그 길이를 통해 확인
    • 개선: height_L 리스트에 숫자를 저장해 확인
  • 건물 보이는지 여부
    • 기존: 2가지 경우(높이가 더 높음 vs 높이가 더 낮음)로 나누어 해결
    • 개선: 1가지 경우만으로 해결

---

참고문헌

-