[BOJ] 1027 고층 건물 (node.js)

링크

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

 

 

문제

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

 

풀이 과정

결국 구해야하는 것은 다른 빌딩을 가장 많이 볼 수 있는 빌딩을 찾고, 그 빌딩에서 보이는 빌딩의 수를 계산하는 것이다.

 

접근법) 전체 빌딩을 순회하면서 볼 수 있는 빌딩의 수를 구하기

가장 직관적인 풀이는 전체 N개의 빌딩을 순회하는 것이다.

상세하게 말하면, 전체 N개의 빌딩을 순회하면서 왼쪽에 있는 빌딩과 오른쪽에 있는 빌딩을 기준으로 하며 (최대 50) 몇 개를 볼 수 있는지 계산한다.

 

이때 연산의 수를 생각해보면 N은 최대 50이고, 각각 왼쪽과 오른쪽까지 쭉 순회한다고 가정하며, 이때 각각의 기준이 되는 빌딩에 대해서도 그 사이에 있는 빌딩들이 시야를 가리지 않는지 체크해야 한다.

빌딩의 수가 최대 50이기 때문에 많아봤자 50*50*50 = 125,000회의 연산이 수행될 것이다.

 

내가 생각한 로직의 예시를 들면 아래와 같다.

빌딩 번호	1번	2번	3번	4번	5번
높이	1	2	7	3	2

위와 같이 빌딩들이 있을 때,

 

3번 빌딩에서 볼 수 있는 빌딩의 갯수를 구한다고 가정하자.

 

그럼 순서대로 1번, 2번, 4번, 5번 빌딩을 볼 수 있는지를 구해야 한다.

아래는 1번 빌딩을 볼 수 있는지를 구하는 경우만 예시로 작성했다.

 

ex) 1번 빌딩을 볼 수 있는지 구하기

이때는 1번과 3번 빌딩을 좌표라고 생각하고 방정식을 구한다.

즉, [1, 1]과 [3, 7]을 지나는 방정식을 구하면 아래와 같다.

 

방정식을 y = ax + b;라고 할 때,

[1, 1]을 대입하면 a + b = 1을,

[3, 7]을 대입하면 3a + b = 7이라는 2개의 식을 구할 수 있다.

 

따라서 y = 3x-2라는 수식을 구할 수 있다.

 

이제는 1번 다음 빌딩부터 3번 이전의 건물을 다시 순회하면서 (위 예시에서는 2번 빌딩만 확인하면 된다)

해당 빌딩의 높이가 방정식의 해보다 높지 않은지 판단해주면 된다.

 

만약 그 사이의 빌딩의 높이가 방정식의 해보다 모두 낮다면(문제의 조건에서 지나거나 접하지 않아야 한다고 했으므로 미만인지 확인)

그 건물은 볼 수 있는 건물이다. 

 

아래는 위의 로직을 코드로 구현한 내용이다.

N의 크기가 작기 때문에 브루트포스로 풀면 된다는 점을 착안하고, 기울기를 구해서 빌딩이 보이는지 처리해야겠다는 아이디어를 생각한다면 쉽게 구현할 수 있는 문제이다.

 

 

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const N = +input[0];
const height = input[1].split(" ").map(Number);

let answer = 0;

for (let i = 0; i < N; i++) {
  const curHeight = height[i];
  let seeCnt = 0;

  for (let left = 0; left <= i - 1; left++) {
    let a = (curHeight - height[left]) / (i - left);
    let b = curHeight - a * i;

    let flag = true;

    for (let mid = left + 1; mid <= i - 1; mid++) {
      if (a * mid + b <= height[mid]) {
        flag = false;
        break;
      }
    }

    if (flag) seeCnt++;
  }

  for (let right = i + 1; right < N; right++) {
    let a = (height[right] - curHeight) / (right - i);
    let b = curHeight - a * i;

    let flag = true;

    for (let mid = i + 1; mid <= right - 1; mid++) {
      if (a * mid + b <= height[mid]) {
        flag = false;
        break;
      }
    }

    if (flag) seeCnt++;
  }

  answer = Math.max(answer, seeCnt);
}

console.log(answer);