https://www.acmicpc.net/problem/1027
-
문제
세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오. -
입력
첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다. -
출력
첫째 줄에 문제의 정답을 출력한다.
한시간 반 정도 삽질 좀 했다,,
기울기랑 y절편 다 구해서 그래프 만들고 그래프 원소들을 하나씩 꺼내서 그 방정식을 다시 x = 0, x = 1, ..., x = n-1 과 비교해서 만나는 점이 없으면 건물이 보이는 걸로 생각하고 카운트해서 이걸 다 세려고 했다...ㅎㅎ...
그래프 만들고 이제 다시 다 비교하려는 찰나에 그럼 포문을 몇개를 해야되는건가 싶기도 하고 시간보고도 아차싶어서 .. 남들은 어떻게 풀었나봤더니 왜이렇게 다들 기막힌 아이디어를 잘 떠올리는걸까?? ㅠㅠ
난 생각도 못했는데 후 ;
암튼 결론은 현재 위치에서 시작하여 오른쪽으로 갈 때 기울기가 반드시 현기울기보다 커야 그 건물을 볼 수 있다 따라서 기울기가 현재보다 큰 경우에만 cnt를 높여주고 현기울기를 갱신해주면 된다 왼쪽도 마찬가지..
그리구 이건 좀 tmi긴한데 제출했는데 런타임에러가 뜨는거임..
그래서 대체 내가 또 어떤 바보짓을 했을까..했더니 일주일동안 그새 싸피문제들에 익숙해져서 나도 모르게 테스트케이스들을 입력받고 뭐.. 그러고 있었따.. 네..
def left(curr): # 왼쪽에 있으면 기울기가 현재보다 작아야만 볼 수 있음
l_cnt = 0 # 보이는 건물 수
max_g = float("inf") # 양의 무한대
for i in range(curr-1, -1, -1): # 거꾸로!!!!!!!!!!꼭
gradient = (arr[curr]-arr[i])/(curr-i)
if gradient < max_g: # 현기울기보다 작으면 보이고 최소기울기는 계속 갱신
max_g = gradient # 갱신
l_cnt += 1 # 보이면 +1
return l_cnt
def right(curr): # 오른쪽에 있으면 기울기가 현재보다 커야만 볼 수 있음
r_cnt = 0 # 보이는 건물 수
min_g = -float("inf") # 음의 무한대
for i in range(curr+1, N):
gradient = (arr[curr]-arr[i])/(curr-i)
if gradient > min_g: # 현기울기보다 크면 보이고 최대기울기는 계속 갱신
min_g = gradient # 갱신
r_cnt += 1 # 보이면 +1
return r_cnt
N = int(input())
arr = list(map(int, input().split()))
ans = 0 # 보이는 건물수 비교할 값
for i in range(N):
sum = left(i) + right(i)
if sum > ans:
ans = sum
print(ans)