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)
view raw 1711.swift hosted with ❤ by GitHub

'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

+ Recent posts