[백준 / BOJ] 1027 고층건물

문제

출처 : www.acmicpc.net/problem/1027

1027번: 고층 건물

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

 

N의 최댓값이 50이여서 완전탐색으로도 풀리는 문제였다.

풀이

한 빌딩에서 볼수있는 최대 빌딩의 값을 전부 갱신해준다.

예를들어, 현재 참조할 건물의 인덱스가 1 이라면,

(1, 2 ~ N) 까지 탐색하며 1번에서 볼수있는 건물의 최대값을 찾아준다.

(1 ,2) (1,3) (1,4)...(1,N)

이때, 볼수있는 건물은 기울기 공식을 이용하여 파악한다.

기울기 공식 : (y증가량 / x증가량)

이후 반복문을 N번 돌리며, 답을 구하면 된다. 

소스코드 

https://github.com/devxb/JJUNalgo/blob/master/%ED%92%80%EC%97%88%EB%8D%98%EA%B2%83%EB%93%A4/1027%20%EA%B3%A0%EC%B8%B5%EA%B1%B4%EB%AC%BC/main.cpp

devxb/JJUNalgo