문제
세준시에는 고층 빌딩이 많다. 세준시의 서민 김지민은 가장 많은 고층 빌딩이 보이는 고층 빌딩을 찾으려고 한다. 빌딩은 총 N개가 있는데, 빌딩은 선분으로 나타낸다. i번째 빌딩 (1부터 시작)은 (i,0)부터 (i,높이)의 선분으로 나타낼 수 있다. 고층 빌딩 A에서 다른 고층 빌딩 B가 볼 수 있는 빌딩이 되려면, 두 지붕을 잇는 선분이 A와 B를 제외한 다른 고층 빌딩을 지나거나 접하지 않아야 한다. 가장 많은 고층 빌딩이 보이는 빌딩을 구하고, 거기서 보이는 빌딩의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 빌딩의 수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 1번 빌딩부터 그 높이가 주어진다. 높이는 1,000,000,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 문제의 정답을 출력한다.
내가 푼 풀이
접근방법: 브루탈포스와 기하학
- 문제에서 힌트를 얻었는데, 두 지붕을 잇는 선분이 있는데, 다른 빌딩이 그 선분을 접하거나 넘으면 안된다고 한다.
- 이는 두 지붕의 x,y좌표를 이용해 두 선을 잇는 직선의 방정식을 구하고, 그 사이의 빌딩들이 그 직선을 접하거나 넘으면 볼 수 없다고 판단한다.
- 직선의 방정식을 구해서 한 빌딩의 지붕 x,y좌표를 대입한다면, 주어진 방적식 y = ax + b 에 대입할 것이다.
- 여기서 대입하여 양쪽의 값을 비교하여 해당 빌딩이 직선을 넘는지, 접점인지 판단한다.
- y >= ax + b 의 경우, 해당 점은 직선과 접한 점이거나, 직선보다 위에 존재하는 점이다. (빌딩을 볼 수 없음)
- y < ax + b의 경우, 해당 점은 직선보다 아래 위치한 점이다. (빌딩을 볼 수 있음)
이 조건을 이용해 모든 경우의수를 따져보고 최댓값을 출력한다.
주의할점) a와 b를 구하고, 값을 비교하는 과정에서 소숫점이 날아가지 않게 적절한 형변환을 해주어야한다.
import Foundation
// 입력받기
let N = Int(readLine()!)!
let buildings = readLine()!.split(separator: " ").map{Int(String($0))!}
var converted = [(x: Int, y: Int)]()
var result = Int.min
// 주어진 빌딩을 지붕의 좌표로 변환
for i in 0..<buildings.count {
converted.append((x: i+1,y: buildings[i]))
}
// 모든 경우 탐색
for i in 0..<converted.count {
var count = 0
for j in 0..<converted.count {
// 같은 빌딩이면 패스
if i == j { continue }
var see = true
let x1: Double = Double(converted[i].x)
let x2: Double = Double(converted[j].x)
let y1: Double = Double(converted[i].y)
let y2: Double = Double(converted[j].y)
// y = ax + b 의 방정식중 a,b를 구하는 과정
let a = (y2 - y1) / (x2 - x1)
let b = y1 - (x1 * a)
// 현재 빌딩 이전에 위치한 빌딩들과의 탐색
if i > j {
for k in j+1..<i {
let leftValue: Double = Double(converted[k].y)
let rightValue: Double = Double(converted[k].x) * a + b
if leftValue >= rightValue {
see = false
break
}
}
} else {
// 현재 빌딩 이후에 위치한 빌딩들과의 탐색
for k in i+1..<j {
let leftValue: Double = Double(converted[k].y)
let rightValue: Double = Double(converted[k].x) * a + b
if leftValue >= rightValue {
see = false
break
}
}
}
if see {
count += 1
} else {
}
}
result = max(result, count)
}
print(result)
'코딩테스트 > 백준' 카테고리의 다른 글
| BOJ-18352 특정 거리의 도시 찾기 Swift (0) | 2024.04.24 |
|---|---|
| BOJ-1916 최소비용 구하기 Swift (0) | 2024.04.24 |
| BOJ-3190 뱀 Swift (0) | 2024.04.22 |
| BOJ-1024 수열의 합 Swift (1) | 2024.04.20 |
| BOJ-1004 어린 왕자 Swift (1) | 2024.04.20 |
