Hyun's_Devlog

https://www.acmicpc.net/problem/1711

브루트포스로 접근한 문제다.

풀이

들어오는 좌표 중 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
}

정답 코드

https://www.acmicpc.net/problem/2166

기하학에 관련된 문제다. 다각형의 면적을 계산하는 방법만 안다면 쉽게 풀 수 있는 문제다.

풀이

https://ko.wikipedia.org/wiki/신발끈_공식

신발끈 공식을 이용하여 풀었다. 다각형을 이루는 모든 꼭지점의 좌표를 알면 좌표를 이용해 다각형을 여러 개의 삼각형으로 쪼개 넓이를 구하는 공식이다.

다각형의 넓이 = ABS(sum1 - sum2) / 2

꼭지점이 시계방향 혹은 반시계 반향으로 순차적으로 주어지게 될 경우, 다음과 같이 순환하는 형태로 줄지어 격자 형태로 곱해서 나온 누적합 sum1, sum2의 차를 2로 나누면 다각형의 넓이를 구할 수 있다. 다행히도 문제에 다각형을 이루는 꼭짓점의 순서대로 입력이 되기에 입력되는 순서 그대로 배열에 담아내면 손쉽게 답을 구할 수 있다.

swift에서는 자릿수 반올림 함수가 제공되지 않으므로 원하는 자릿수에서 반올림 하기위해 직전 자릿수까지 10을 곱해준 뒤 반올림 함수 round()를 이용하였고 다시 자릿수만큼 나누어 주었다.

정답 코드