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

문제

1027번: 고층 건물

---

1. 첫 번째 풀이

사고 과정

- N이 50밖에 안 됨 -> 모두 돌려보자

- 일단 양 옆 건물은 무조건 보인다.

- 왼쪽 먼저 살펴보자. i번째 건물과 i-1번째 건물의 높이 차를 h에 저장해둔다. ([i-1] - [i])

- 비교 방법은 두 가지.

1. i와 i-2의 차이를 2 * h와 비교한다.

2. i-1와 i-2의 차이를 h와 비교한다.

- 둘 모두 h보다 크다면 볼 수 있고, 작거나 같다면 볼 수 없다. 볼 수 있는 경우 h를 갱신한다.

- 둘 중 결과가 정확히 나오지 않는 사례를 찾아보자.

- 2, 5, 3, 8을 2에서 볼 때, 1의 방법으론 5밖에 안 보이지만 2의 방법에선 8도 볼 수 있게 나온다. 실제로 볼 수 있는 건 5뿐이므로 1의 방법으로 구현하자.

 

1. n, h, count를 선언, 빌딩 배열을 입력받는다.

2. 0부터 n-1까지 반복문을 돌린다. (i)

3. 내부에 반복문을 하나 더 돌린다. (j). i와 j를 비교하고, 높이 차 중 가장 큰 걸 h에 저장한다.

4. h와 건물의 높이 차를 비교하며 볼 수 있는 건물을 카운트한다.

 

코드

#include <stdio.h>
#include <vector>

int main() {
	int n, h, max = 0;
	scanf("%d", &n);
	std::vector<int> buildings(n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &buildings[i]);
	}
	
	for (int i = 0; i < n; i++) {
		int count = 0;
		// 왼쪽 바라보기
		if (i != 0) {
			count++;
			h = buildings[i - 1] - buildings[i];
			for (int j = i - 1; j >= 0; j--) {
				int newH = buildings[j] - buildings[i];
				if (newH > (i - j) * h) {
					count++;
					h = newH / (i - j);
				}
			}
		}

		// 오른쪽 바라보기
		if (i != n - 1) {
			count++;
			h = buildings[i + 1] - buildings[i];
			for (int j = i + 1; j < n; j++) {
				int newH = buildings[j] - buildings[i];
				if (newH > (j - i) * h) {
					count++;
					h = newH / (j - i);
				}
			}
		}
		
		max = (count > max) ? count : max;
	}

	printf("%d", max);
}

 

결과

예제는 모두 맞았는데 틀렸습니다가 나왔다.

 

반례를 찾아보자.

---

2. 두 번째 풀이 (마지막 풀이)

사고 과정

- / 연산에서 오차가 생겼나?

- 만약 i에서 오른쪽을 바라볼 때, i + 3과의 높이 차가 4라면, h에는 1이 입력될 것이다. 그럼 i + 4와 5만큼 차이날 때, 실제론 보이지 않지만 보인다고 판정할 수 있다.

- 그럼 h를 double로 바꾸면 해결될까?

 

코드

#include <stdio.h>
#include <vector>

int main() {
	int n, max = 0;
	double h;
	scanf("%d", &n);
	std::vector<int> buildings(n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &buildings[i]);
	}
	
	for (int i = 0; i < n; i++) {
		int count = 0;
		double newH;
		// 왼쪽 바라보기
		if (i != 0) {
			count++;
			h = buildings[i - 1] - buildings[i];
			for (int j = i - 1; j >= 0; j--) {
				newH = buildings[j] - buildings[i];
				if (newH > (i - j) * h) {
					count++;
					h = newH / (i - j);
				}
			}
		}

		// 오른쪽 바라보기
		if (i != n - 1) {
			count++;
			h = buildings[i + 1] - buildings[i];
			for (int j = i + 1; j < n; j++) {
				newH = buildings[j] - buildings[i];
				if (newH > (j - i) * h) {
					count++;
					h = newH / (j - i);
				}
			}
		}
		
		max = (count > max) ? count : max;
	}

	printf("%d\n", max);
}

 

결과

자료형이 문제였다.

---

개선

사고 과정

- 로직에 비해 코드 길이가 너무 길다. 줄여볼 수 없을까?

- 핵심 로직은 결국 좌우 2번의 for문. 이걸 통합할 수 있을까?

- 로직을 함수로 분리하고, 매개 변수 순서를 조건에 따라 바꿔 넣으면 가능할 것 같다.

- 하지만 결국 왼쪽, 오른쪽 반복문은 따로 돌려야 했다.

- 고치다보니 결국 마지막 코드와 같아져서 그만두기로 했다.

---

가장 효율적인 코드

https://www.acmicpc.net/source/4549238

choyi0521님의 코드. C++로 당당히 1위를 차지하셨다.

 

코드 분석

- 모든 (i, j) 쌍을 비교한다.

- 두 빌딩이 서로 보이는 빌딩이라면, 배열 b에 i, j를 1씩 더해준다.

- 배열 b의 최댓값을 출력한다.

- 천잰가?

 

내 코드와 비교

1. 내 코드는 i -> j와 j -> i를 두 번 계산한데 비해, 위 방법은 한 번만 계산하고 끝냈다.

2. 내 코드는 모든 빌딩 순회에 1번, 내부에서 다른 모든 왼쪽 빌딩과 비교하며 2번, 다른 모든 오른쪽 빌딩과 비교하며 총 3번의 반복문이 돌아갔는데, 그에 따라 코드의 길이도 길어졌다. 하지만 choyi0521님의 코드는 매우 깔끔하다.

3. t(나의 h) = -9e9로 초기화해 양 옆 빌딩도 항상 포함시켰다.

4. cstdio를 포함해 C++에서 C 함수를 사용하셨다.

---

강평

세상은 넓고 고수는 많았다. 아예 새로운 풀이법을 알게 되어 상당히 기분 좋은 날. 이 방법은 다른 문제에도 널리 쓸 수 있을 것 같다. 문제 자체는 구현에 가까운 편