본문 바로가기

3차원 기하학3

[자바] 백준 9715 - 면적 구하기 (boj java) 문제 : boj9715 이하의 예시를 확인해보자. 2 3 312 103 그림으로 그려보면 아래와 같다. 면적, 즉 다른 상자에 닿아있지 않고 공기(?)와 닿아있는 면의 수를 세면 될 것이다. 우선 어떻게 해야 면적을 구할 수 있을지 생각해보자. 우선 가장 간단한 바닥에서 위로 본 형태와, 위에서 바닥쪽으로 본 형태부터 생각해보자. 둘 다 아래와 같이 2차원 평면의 형태로 보일 것이다. 따라서 0이 아닌 위치라면 면은 항상 +2를 해주면 된다(바닥 하나 뚜껑 하나). 그럼 이제 동서남북 4개의 방향에서 공기와 닿아있는 면을 세주면 된다. 우측에서 좌측으로 보는 경우를 한번 생각해보자. 아래 그림과 같은 방향이다. 설명을 돕기 위해 판이 하나 이동하면서 본다고 해보면, 아래와 같은 두 가지 부분에서 면이 공.. 2022. 5. 31.
[자바] 백준 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.