Algorithm Test/백준

[백준] 1027. 고층 건물 (JAVA)

김맷돌 2021. 5. 6. 22:09
반응형

🏙 고층 건물

 


문제

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

 

입력

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

 

출력

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

 


🔑 IDEA

건물 A에서 건물 B가 보인다면, 건물 B에서도 건물 A가 보인다.

👉 인덱스가 증가하는 방향으로만 검사하면 된다. 

 

1. 건물 A에서 건물 B를 볼 수 있으려면 저장된 slope보다 A-B의 기울기가 커야 한다.

2-1. 건물 B가 보이지 않으면 다음 건물을 검사한다. 

2-2. 건물 B가 보인다면, visible[A]와 visible[B]를 1씩 증가시키고 slope를 A-B의 기울기로 갱신한 뒤 다음 건물을 검사한다. 

 

💡  나의 풀이

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class Main {
	static int N;
	static int[] building;
	static int[] visible;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		building = new int[N];
		visible = new int[N];

		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			building[i] = Integer.parseInt(st.nextToken());
		}
		count();

		Arrays.sort(visible);
		System.out.println(visible[visible.length-1]);
	}

	private static void count() {
		for(int i=0; i<N-1; i++) {
			visible[i] += 1; //바로 옆 건물은 무조건 보인다.
			visible[i+1] += 1;
			double slope = building[i+1]-building[i];
			for(int j=i+2; j<N; j++) {
				double nextSlope = (double)(building[j]-building[i])/(j-i);
				if(nextSlope <= slope) continue;
				slope = nextSlope;
				visible[i]++;
				visible[j]++;
			}
		}
	}
}

 

 


 

 

1027번: 고층 건물

세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)

www.acmicpc.net

 

반응형