[자바] 백준 13552 - 구와 쿼리 (boj java)
문제 : boj13552 처음엔 시간 제한을 안보고 다음과 같이 생각했다. x,y,z값을 sqrt(1000000)정도씩 구간을 나눠서 연산을 줄이면 어찌저찌 되지 않을까 싶었다. 하지만, 시간 제한을 보니 출제 의도가 그냥 한번 해보라는 것 같았다. 모든 경우를 살펴본다고 하면, O(NM)으로 사실 무리가 있을 것 같긴 했는데, 시간 제한이 20초나 되므로 일단 해보기로 했다(자바의 경우 주어진 시간 x2+1초 이므로 총 41초 제한이다.). 그래도 만만치 않은 수치이므로 입출력 모두 빠르게 되도록 짰고, 연산이 느리고 불명확해서 틀릴 가능성이 있는 double을 사용하지 않도록 짰다. 참고로 3차원에서 두 점 (a,b,c), (x,y,z)의 거리는 (A)와 같이 구할 수 있다. 이 문제에서는 반지름이 ..
2022. 5. 13.
[자바] 백준 11880 - 개미 (boj java)
문제 : boj11880 문제에서 제시된 직육면체에서 A에서 B로 가는 최단 거리를 어떻게 구할 수 있을까? 직육면체를 전개해서 살펴보면 어렵지 않게 피타고라스의 정리만 가지고 최단거리의 길이를 구해낼 수 있다. 다만 이 문제에서는 '서로 반대편에 위치한 A, B점까지의 최단 거리' 라고 했으므로 A, B점은 임의로 변경해도 된다고 볼 수 있다(정확힌 틀려보고 알았다 ㅠㅠ). 그렇다면 그냥 3개의 변의 길이가 주어졌을 때, 위의 x^2+(y+z)^2이 최단이 되는 값을 찾으면 된다(x,y,z에 각각 a,b,c를 넣었을 때). 즉, 이하의 3가지 중 최단 거리를 찾으면 된다. a,b,c 3가지 중 2가지를 택하므로 3C2 = 3가지 경우를 모두 살펴봐서 최단거리를 구하면 된다. 다만 이 경우 직관적으로 x..
2022. 5. 11.
