이 문제는 피타고라스 정리를 이용해서 특정값을 구하는 것 입니다.
- Basic : a+b+c = 1000 이고 a^2 + b^2 = c^2 인 abc의 곱을 구하기
- Advance : Test Case가 3000개 이하 이고, a+b+c <= 3000 이하인 조건에서 abc의 곱의 최대값을 구하기
우선 간단하게 Basic을 풀어보도록 하겠습니다. Basic의 결과에 따라서 동일한 로직으로 Advance를 구현할지... 아니면 전체 로직을 개편해서 구할지 생각해야 합니다.
1. Basic
나름 머리를 써본다고, loop를 줄여할 항목을 생각해 봅니다.
- 삼각형의 가장 긴 변의 길이는 보수적으로 생각해 볼때, 정삼각형 보다 크며 ~ 전체 길이 합보다 작다
- 가장 긴 변의 길이가 정해 질때, 그 길이의 제곱수가 나머지 변들의 조합의 가장 큰 경우보다 크면 연산을 중지한다
- 가장 긴 변을 제외한 나머지의 값의 반을 기준으로 ~ 0이 될때까지 경우를 구하며 제곱수의 합이 같을 때 저장한다
##### P9
import time
if __name__ == '__main__':
tc = int(input())
for t in range(tc):
n = int(input())
start = time.time()
n = 3000
res = []
for i in range(n//3, n):
if i**2 > 1 + (n-i-1)**2: break
for j in range((n-i)//2, 0, -1):
if i**2 == j**2 + (n-i-j)**2:
res.append([j, (n-i-j), i])
break
maxAns = 0
for i in range(len(res)):
temp = res[i][0] * res[i][1] * res[i][2]
if temp > maxAns: temp, maxAns = maxAns, temp
if len(res) ==0: print(-1)
else: print(maxAns)
end = time.time()
print("{0:.5f}".format(end-start))
#target : 1000 , time : 0.04619
#target : 3000 , time : 0.38497이렇게 하면, 문제가 생깁니다. 왜냐하면, Advance의 경우 최대 3,000개의 Test Case가 있기때문에... 막말로 최대 1000초도 걸릴수 있는 거니까요... 그렇다면 어떻게 해결해야 할까요??
2. Advance
매번 loop를 이정도 규모로 돌리게 되면, 당연히 Timeout이 발생하게 될 것입니다. 그렇다면!! 그냥 한번에 다 구해놓고... 저장된 공간에서 빼서쓰는건 어떨까요?? 이걸 전에도 말한 Memoization이라고 합니다. 그럼 어떻게 적용하면 될까요??
- 작은 한개의 변을 1부터 3000까지 loop를 돌린다
- 다른 변의 크기는 위의 한변의 크기 이상부터 3000 - i 까지 돌린다 (1부터 돌리지 않는건 어차피 앞에서 구했기 때문입니다. 예를들어 24, 36의 조합을 구했는데... 다시 36, 24의 조합을 구할필요는 없으니까요.)
- 구한 값의 제곱의 합이 자연수로 root값이 구해진다면...!! 그 합이 목표치보다 작은지만 확인해서 기존에 값이 있는지 확인하고 최대값이 경우 저장합니다.
import math
def preCalc(target):
res = [-1] * (target+1)
for i in range(1,target):
for j in range(i, target-i):
squareAB = i*i + j*j
sqrtC = math.sqrt(squareAB)
if sqrtC % 1 == 0:
sumABC = i+j+int(sqrtC)
if sumABC <= target:
mulABC = i*j*sqrtC
if mulABC > res[sumABC]: res[sumABC] = mulABC
return res
if __name__ == '__main__':
memRes = preCalc(3000)
tc = int(input())
for t in range(tc):
req = int(input())
print(int(memRes[req]))
의외로 간단하죠?? 이렇게 하면 초기에 구하는 시간만 걸리고, 나머지 Test Case에 대해서는 10^9 정도가 있어야 1초정도 걸릴 것입니다.
-Ayotera Lab-
댓글