
https://www.acmicpc.net/problem/1711
1711번: 직각삼각형
첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,500)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 주
www.acmicpc.net
브루트포스로 접근한 문제다.
풀이
들어오는 좌표 중 3개를 선택하는 조합 반복문을 생성. 피타고라스의 정리를 사용해 직각 삼각형인지 판별하면 된다.
단 해당 문제에서 흥미로웠던 점은 세 점 A, B, C의 조합에서 나온 3가지의 선분(AB, BC, AC) 중 가장 긴 선분을 찾아내는 부분에서 시간초과가 났다.
처음에는 단순히 3개의 선분의 길이를 배열에 담아낸 뒤 내림차순 정렬하여 (0번 원소 == 1번 원소 + 2번 원소) 조건문으로 판별하였으나, 시간초과가 발생.
func isRightTriangle(a:(Int,Int),b:(Int,Int),c:(Int,Int)) -> Bool{
let AB = ((a.0-b.0)*(a.0-b.0)) + ((a.1-b.1)*(a.1-b.1))
let AC = ((a.0-c.0)*(a.0-c.0)) + ((a.1-c.1)*(a.1-c.1))
let BC = ((b.0-c.0)*(b.0-c.0)) + ((b.1-c.1)*(b.1-c.1))
let tmp = [AB,AC,BC].sorted(by: >)
return tmp[0]==tmp[1]+tmp[2] ? true:false
}
이때부터 조금 헤맸다. 시간복잡도를 계산해 보면 입력좌표는 최대 1500개가 입력. 1500C3 = 561,375,500 여기서 각 조합마다 정렬이 이루어지는데, Swift 배열의 정렬 함수 시간복잡도는 0(N)이므로 대략 16억 번의 수행이 이루어진다. 보통 알고리즘 문제를 풀 때 러프하게 1초당 1억 번의 연산으로 계산하게 되는데, 5초의 시간은 턱없이 부족한 시간인 것이다.
그러다 문득 배열을 생성하고 정렬하는 것보단 비트연산이 더욱 빠르겠다는 생각이 들어 아래와 같이 수정하였더니 통과하였다.
func isRightTriangle(a:(Int,Int),b:(Int,Int),c:(Int,Int)) -> Bool{
let AB = ((a.0-b.0)*(a.0-b.0)) + ((a.1-b.1)*(a.1-b.1))
let AC = ((a.0-c.0)*(a.0-c.0)) + ((a.1-c.1)*(a.1-c.1))
let BC = ((b.0-c.0)*(b.0-c.0)) + ((b.1-c.1)*(b.1-c.1))
// let tmp = [AB,AC,BC].sorted(by: >)
// return tmp[0]==tmp[1]+tmp[2] ? true:false
let res = (AB==AC+BC) || (AC == AB+BC) || (BC==AB+AC)
return res ? true:false
}
정답 코드
import Foundation | |
//by rhyno | |
final class FileIO { | |
private let buffer:[UInt8] | |
private var index: Int = 0 | |
init(fileHandle: FileHandle = FileHandle.standardInput) { | |
buffer = Array(try! fileHandle.readToEnd()!)+[UInt8(0)] // 인덱스 범위 넘어가는 것 방지 | |
} | |
@inline(__always) private func read() -> UInt8 { | |
defer { index += 1 } | |
return buffer[index] | |
} | |
@inline(__always) func readInt() -> Int { | |
var sum = 0 | |
var now = read() | |
var isPositive = true | |
while now == 10 | |
|| now == 32 { now = read() } // 공백과 줄바꿈 무시 | |
if now == 45 { isPositive.toggle(); now = read() } // 음수 처리 | |
while now >= 48, now <= 57 { | |
sum = sum * 10 + Int(now-48) | |
now = read() | |
} | |
return sum * (isPositive ? 1:-1) | |
} | |
} | |
var io = FileIO() | |
let N = io.readInt() | |
var points = [(Int,Int)]() | |
var ans = 0 | |
func isRightTriangle(a:(Int,Int),b:(Int,Int),c:(Int,Int)) -> Bool{ | |
let AB = ((a.0-b.0)*(a.0-b.0)) + ((a.1-b.1)*(a.1-b.1)) | |
let AC = ((a.0-c.0)*(a.0-c.0)) + ((a.1-c.1)*(a.1-c.1)) | |
let BC = ((b.0-c.0)*(b.0-c.0)) + ((b.1-c.1)*(b.1-c.1)) | |
// let tmp = [AB,AC,BC].sorted(by: >) | |
// return tmp[0]==tmp[1]+tmp[2] ? true:false | |
let res = (AB==AC+BC) || (AC == AB+BC) || (BC==AB+AC) | |
return res ? true:false | |
} | |
for _ in 0..<N{ | |
let point = [io.readInt(), io.readInt()] | |
points.append((point[0],point[1])) | |
} | |
for a in 0..<N-2{ | |
for b in a+1..<N-1{ | |
for c in b+1..<N{ | |
if isRightTriangle(a: points[a], b: points[b], c: points[c]){ ans += 1 } | |
} | |
} | |
} | |
print(ans) |

'Problem Solving > BOJ' 카테고리의 다른 글
[14719] 빗물 (0) | 2023.06.02 |
---|---|
[5719] 거의 최단 경로 (0) | 2023.04.30 |
[16169] 수행시간 (0) | 2023.04.11 |
[24526] 전화 돌리기 (0) | 2023.04.05 |
[14907] 프로젝트 스케줄링 (0) | 2023.04.03 |