[C++/백준] 고층 건물

 

1027번: 고층 건물

 

[문제]

 

요약하면, 빌딩들이 있고 그 빌딩에서 다른 빌딩이 보이는가 이다. 

(지붕을 이었을 때, 다른 빌딩으로 가로막혀 있거나 다른 빌딩이 선분 위의 점이면 안됨..)

 

[문제 풀이]

문제를 보고 딱 떠오른게 기울기로 푸는 거다

문제의 조건인, "지붕을 이었을 때, 다른 빌딩에 닿으면 안된다" 라는 조건에서 각도를 생각할 수 있었는데, 

해당 조건에 걸리지 않으려면 

 

처음을 기준으로 쳤을 때 위의 그림처럼 앞선 빌딩들 보다 이루는 각이 크면 된다 ㅇㅇ 이건 작을 때도 적용된다.

각도가 크다는건 => 기울기가 크다는 거니까, 

건물 사이를 x좌표, 높이를 y좌표로 두면 기울기를 구할 수 있고,

첫 번째 건물부터 기준을 두고 뒤의 빌딩들 사이에서 앞선 최대 기울기보다 큰 기울기를 가진 건물을 찾아내면 되는거다.  

 

y를 ( 기준건물 - 다른 건물 ) 로 두면, 나보다 낮을 때는 기울기가 -,  클 때는 +가 되고

낮을 경우에도 똑같이 큰가?를 조건으로 구할 수 있게 된다. 

 

그 다음으로 빌딩들을 돌아가면서 찾아주는데, 기준 건물에서 보이는 건물은 보이는 건물에서도 기준 건물이 보인다는 의미이기도 하기 때문에 동시에 수를 추가해주면 된다. 

 

[전체 코드]

#include<iostream>
#include<algorithm>

using namespace std;

#define INF 1e9;

int N;
long double height[52];
long long view[52];
long long ans = 0;

int find_view(int n) {
	long double now = -INF;
	for (int i = n+1; i < N; i++) {
		long double h = (height[i] - height[n]) / (i - n);
		// long double h = (static_cast<long double>(height[i]) - height[n]) / (i - n);
		if (now < h) {
			view[i]++;
			view[n]++;
			now = h;
		}
	}
	ans = max(ans, view[n]);

	return 0;
}

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> height[i];
	}

	fill(view, view + N, 0);

	for (int i = 0; i < N; i++) {
		find_view(i);
	}

	cout << ans;
}

 

---

[++추가 및 고찰]

여전히 형변환이 좀 어려운데 문제를 풀면서 실패가 떴었다. 그 이유가 형변환 때문이었음. 

이 부분에서, height의 자료형을 long long으로 해줬었는데 그렇다보니 계산 과정에서 손실이 일어났다고 한다. 

long double h = (long long)/int 이렇게 되니까, 내부에서 long long/ int 로 계산하는 과정에서 소수점 손실이 한 번 일어나고, h에 들어간 것 같다. 

 

그래서 height의 자료형을 long double로 바꿔주거나 static_cast<long double>을 붙여서 진행해 주면 된다고 한다. 

 

솔직히 IDE를 써서 알았지,,, 프로그래머스에 나오는 문제였으면 풀지 못했을 것 같다... ㅠㅠ 

 

=> 자료형을 주의하자..!