크기가 각각 a, b, c인 여러 개의 정육면체(큐브)를 쌓아 가로 a, 세로 b, 높이 c인 새로운 직육면체 상자를 만들었다고 가정해 보겠습니다. 이때 a, b, c는 쌍별로 서로소(공약수가 1) 관계여야 합니다. 즉, gcd(a, b) = gcd(b, c) = gcd(a, c) = 1을 만족합니다.
그림과 같이 꼭짓점 P, Q, R을 지나는 하나의 평면으로 상자를 딱 한 번 절단하여 두 조각으로 나누어야 합니다. 이렇게 잘랐을 때 몇 개의 큐브가 두 조각으로 잘리는지 구하는 것이 바로 이 문제의 목표입니다. 가능한 세 변의 길이 조합을 담은 배열이 입력으로 주어지며, 각 경우에 대해 정답을 계산해야 합니다.
예를 들어 n = 3이고 input_array = [[1, 2, 3], [4, 2, 5], [6, 8, 2]]라면 출력은 [5, 18, 37]이 됩니다. 세 개의 서로 다른 사례가 주어졌으며, 그림과 같은 방식으로 잘랐을 때 각각 5개, 18개, 37개의 큐브가 절단됩니다.
풀이 접근 방법
절단면은 각 축 방향으로 격자 평면들을 통과하므로, 잘리는 큐브의 개수는 세 변의 곱들의 조합으로 계산할 수 있습니다. 중복되는 부분을 제거하기 위해 1을 빼고 2로 나누며, 값이 매우 커질 수 있으므로 마지막에 1000000007로 나눈 나머지를 취합니다. 전체 과정은 다음과 같습니다.
- 결과를 저장할 빈 리스트(output)를 준비합니다.
- i를 0부터 n-1까지 반복하면서 다음을 수행합니다.
- a := input_array[i][0]
- b := input_array[i][1]
- c := input_array[i][2]
- val := ((a × b + a × c + b × c − 1) ÷ 2의 내림값) mod 1000000007
- val을 결과 리스트의 끝에 추가합니다.
- 결과 리스트를 반환합니다.
예제 코드
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
from math import ceil
def solve(n, input_array):
output = []
for i in range(n):
a, b, c = input_array[i][0], input_array[i][1], input_array[i][2]
val = ((a * b + a * c + b * c - 1) // 2 % 1000000007)
output.append(val)
return output
print(solve(3, [[1, 2, 3], [4, 2, 5], [6, 8, 2]]))
입력
3, [[1, 2, 3], [4, 2, 5], [6, 8, 2]]
출력
[5, 18, 37]