[백준]1027번 고층 건물 - C/C++

https://www.acmicpc.net/problem/1027

1027번: 고층 건물

문제

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

입력

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

출력

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

---

다른 고층 빌딩을 지나거나 접하지 않아야 한다고 했기 때문에 좌표간의 기울기로 문제에 접근하면 된다.

왼쪽 건물들의 경우 기준점이 되는 건물( i )과 판별하는 건물( a ) 사이의 건물( b )들 중 해당 기울기보다 더 작은 기울기가 있다면 해당 건물은 보이지 않는다.

오른쪽 건물들의 경우 더 큰 기울기가 있다면 해당 건물은 보이지 않는다. 

 

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

int N,ans=0;
int arr[51];

void solve() {
	for (int i = 1; i <= N; i++) { // 기준 건물
		int tmp = 0;
		for (int a = 1; a < i; a++) { // 보이는 지 확인하는 대상
			if (a == i) continue;
			bool flag = true;
			double grad_a = (arr[i] - arr[a]) / (double)(i - a);
			for (int b = a+1; b < i; b++) { // 그 사이 건물
				double grad_b = (arr[i] - arr[b]) / (double)(i - b);
				if (grad_a >= grad_b) {
					flag = false;
					break;
				}
			}
			if (flag) {
				tmp++;
			}
		}
		for (int a = i+1; a <= N; a++) { // 보이는지 확인하는 대상
			if (a == i) continue;
			bool flag = true;
			double grad_a = (arr[a] - arr[i]) / (double)(a - i);
			for (int b = i + 1; b < a; b++) { // 그 사이 건물
				double grad_b = (arr[b] - arr[i]) / (double)(b - i);
				if (grad_a <= grad_b) {
					flag = false;
					break;
				}
			}
			if (flag) {
				tmp++;
			}
		}
		ans = max(tmp, ans);
	}
	cout << ans;
}

int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	solve();
}

---

오늘은 분류를 보지 않고 문제를 풀기 위해 solved.ac에서 골드 4 문제 중 하나를 선별해서 풀었다. 접하는 것과 보이는 것을 구하는 문제여서 기울기를 구하여 풀 수 있다고 생각했다.

처음에는 왼쪽과 오른쪽의 for문을 나누었다가 코드를 깔끔하게 작성하고 싶어 반복문을 하나로 병합하였다. 하지만 좌측과 우측의 비교 기준이 달라 한 가지 for문을 사용하려면 되려 코드의 가독성도 떨어지고 그림까지 그리면서 코드를 작성하였지만 지금 확인하고 있는 건물이 i, a, b 총 세 개인데 비교 기준까지 다르게 하려니 굉장히 헷갈렸다. 그래서 두 부분으로 나누었더니 코드가 더욱 직관적으로 작성된 것 같았다. 코드의 길이와 코드의 가독성을 잘 조율해서 코드를 짜야겠다고 생각했다! 

그리고 중간에 double 값을 할당해 주었지만 int 값들을 나누어버려서 분수 표현이 제대로 되지 않았다. 분수가 나오는 경우를 많이 접해보지 못해서 이런 기초적인 실수를 한 것 같다. 앞으로 인지하고 있어야겠다!