728x90
https://www.acmicpc.net/problem/1027
문제
세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.
생각
- 맨 왼쪽부터 오른쪽 건물이 보이는 경우의 수를 생각한다.
- 보이는 건물에 각각 +1을 해준다.
- 그러면 왼쪽의 건물은 고려할 필요 없이 오른쪽 건물들만 고려하면 된다. (브루트포스)
- 또한 문제에서 접선의 얘기가 나왔으므로 기울기가 앞 건물보다 높아야한다.
- 기울기를 구해야 하므로 타입을 int가 아닌 double로 해주어야한다. (중요)
** 현재 건물에서 다음 건물(i)이 보이려면 다음과 같은 조건을 만족해야한다.
- 앞에 계산한 기울기의 각도(i-1)보다 다음 건물의 기울기(i)가 더 커야한다.
풀이
- N개의 건물이 아닌 N-1개의 건물에 대해 볼 수 있는 오른쪽 건물 수를 계산한다. : sol()
- 해당 건물을 기준으로 for문을 통해 오른쪽 건물과의 기울기를 비교하여 기울기의 각도가 점점 높아지는 건물들만 계산하면된다. : process()
- for문안에서 현재 건물과 타겟 건물의 기울기를 구한다. 이때 double타입을 사용해야한다. : get_incline()
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
typedef long double ld;
using namespace std;
int N;
vector<ll> buildings;
vector<int> check;
void input(){
cin >> N;
check = vector<int>(N,0);
for(int i = 0; i < N; i++){
int tmp;
cin >> tmp;
buildings.push_back(tmp);
}
}
//현재 건물에서 오른쪽 건물만 고려하므로 뺄셈의 순서를 고려해 주었다.
ld get_incline(int target_idx, int current_idx){
ld x = current_idx - target_idx;
ld y = buildings[current_idx] - buildings[target_idx];
return y / x;
}
void process(int target_idx){
check[target_idx] += 1;
check[target_idx+1] += 1;
ld incline = get_incline(target_idx, target_idx+1);
for(int i = target_idx+2; i < N; i++){
ld tmp = get_incline(target_idx, i);
if(tmp > incline){
incline = tmp;
check[target_idx] += 1;
check[i] += 1;
}
}
}
void sol(){
//맨 오른쪽 건물은 비교할 대상이 없으므로 N-1까지만 반복문 실행
for(int i = 0; i < N-1; i++){
process(i);
}
int answer = 0;
for(int i = 0; i < N; i++){
answer = max(answer, check[i]);
}
cout << answer;
}
int main(){
input();
sol();
return 0;
}
728x90
'알고리즘 문제 > 완전탐색' 카테고리의 다른 글
[개쉬운 풀이] 백준 15683 감시 CPP (11일차) (0) | 2024.12.02 |
---|---|
[개쉬운 풀이] 백준 22251 빌런 호석 (2) | 2024.09.28 |
[개쉬운 풀이] 백준 2116 주사위 쌓기 (2) | 2024.03.05 |