[백준/Python] 11880 - 개미

문제

승현이는 방학을 맞아 심심하지만, 공부는 하기 싫습니다. 이렇게 방 안에서 하루하루 시간을 낭비하던 중, 승현이는 자신의 직육면체 모양의 지우개에 개미 한 마리가 붙어 있다는 것을 알게 됩니다. 사실 이 개미는 우리가 문제를 어떻게 낼 지 잘 몰라서 방에 넣은 로봇입니다.

이 개미 로봇은 말도 안 되지만 어떠한 시련이 닥쳐도 서로 반대편에 위치한 점 A에서 점 B까지 최단 거리로 이동하며 그 경로를 지우개에 그립니다. 누군가 자신의 지우개에 흔적을 남기는 것을 너무나 싫어하는 승현이는 개미 로봇이 자신의 지우개에 남긴 흔적의 양, 즉 로봇이 이동한 거리를 구하여 우리에게 손해 배상 청구를 하려고 합니다. 개미 로봇은 부피가 존재하지만, 승현이는 정확한 양을 측정하기 귀찮기 때문에 그냥 부피가 없다고 처리하기로 했습니다.

우리에게 복수하고 싶어하는 승현이를 도와줍시다.

입력

첫 줄에 테스트 케이스의 수 T가 주어집니다. (1 ≤ T ≤ 100,000)

각 테스트 케이스마다 한 줄에 하나씩 음이 아닌 정수 a, b, c가 공백을 사이로 두고 주어집니다. 여기서 a는 지우개의 가로의 길이, b는 지우개의 세로의 길이, c는 지우개의 높이를 나타냅니다. (1 ≤ a, b, c ≤ 105)

출력

각 테스트 케이스마다 한 줄에 하나씩 개미 로봇이 이동한 거리를 출력합니다. 단 꼼꼼한 승현이는 오차가 생기는 것을 원하지 않으므로, 이 거리의 제곱을 출력해야 합니다.

예제 입력 1

1
1 2 3

예제 출력 1

18

정답 코드

input = __import__('sys').stdin.readline
t = int(input())
for i in range(t):
    a, b, c = map(int, input().split())
    baseA = (a ** 2) + ((b + c) ** 2)
    baseB = (b ** 2) + ((a + c) ** 2)
    baseC = (c ** 2) + ((a + b) ** 2)
    answer = min(baseA, baseB, baseC)
    print(answer)

풀이

처음에는 '개미 로봇이 지우개에 남긴 흔적의 양' 을 구하라는 것을, 개미가 어느 한 꼭짓점에서 출발하여 지우개 안을 파먹으면서 반대편 꼭짓점으로 이동하는 수직 경로를 구하라는 것으로 이해했습니다. 이 경우에는 직육면체의 대각선 길이의 제곱을 구하면 되므로 a, b, c를 모두 제곱해서 더하면 됩니다.

예제 입력의 경우 1과 2와 3을 모두 제곱해서 더하면 1 + 4 + 9 = 14가 나오는데...

???

이는 예제 출력과 다릅니다.

사실 작아서 잘 안 보이는 그림에 함정이 숨어있습니다.

게미는 지우개를 관통해서 이동하는 것이 아니라 표면을 걸어가며 이동합니다.

정답 비율이 낮아서 고른 문제였는데 알고보니 예시 그림이 이해하기 어렵게 표현돼있어서 낮았던...

그러면 문제를 제대로 이해하였으니 한 꼭짓점에서 다른 꼭짓점까지 이동하는 직선 최단 경로를 구해봅시다. 예제 입력의 가로 1, 세로 2, 높이 3의 직육면체의 전개도를 그려보면

예제 입력 - 가로: 1 세로:2 높이:3

다음과 같습니다.

이 때, 한 꼭짓점과 다른 꼭짓점의 직선 최단 경로를 구하려면 그냥 직각삼각형의 대각선 길이의 제곱을 구하면 됩니다.

밑변이 가로인 경우와 (1 ^ 2) + ((2 + 3) ^ 2) = 26

밑변이 세로인 경우 (2 ^ 2) + ((1 + 3) ^ 2) = 20

밑변이 높이인 경우 (3 ^ 2) + ((1 + 2) ^ 2) = 18

이 중 무조건 최단 경로로 이동한다고 하였으므로 최솟값인 18이 정답이 됩니다.

즉, 한 변을 밑변으로하는 나머지 두 변의 합을 높이로 하는 직각삼각형의 대각선 길이의 제곱을 각각 구해주고

최소값을 찾아 출력해주면 됩니다.

정답 비율에 비해 문제 난이도가 너무 쉬운 경우였네요.