이번 문제는 왠지 간단한 것 같지만, 제약조건을 두자면 한없이 어려워지는 문제인거 같습니다. 우선 아직까지는 basic한 방식으로만 생각이 나서 해당 방법으로 우선 통과를 하고, 제약조건을 두어 Time Limit에 영향이 없도록 고려해서 한번더 올려보도록 하겠습니다.
- 주어진 조건만 만족하도록, 100까지의 Sum square difference 구하기
- 제약조건을 두어 Test case가 10000개의 Test case에 최대 10000까지 구하기 (time out 발생가능)
1. Basic
그냥 단도직입 적으로 구합니다. 단 python을 이용하니... 이 언어에서 가능한 편한 방식으로 구현해 보겠습니다. python에는 배열을 신규로 생성할때, 내부 함수를 통해서 새로운 배열의 생성이 가능합니다.
또한, sum( )함수로 가볍게 더해보도록 하겠습니다.
def calcSquare(target):
scaleRange = range(1, target+1)
squareSum = sum(i**2 for i in scaleRange)
sumSquare = sum(scaleRange)**2
return sumSquare-squareSum
if __name__== '__main__':
tc = int(input())
for i in range(tc):
target = int(input())
print(calcSquare(target))1부터 target까지 순차적으로 증가하는 숫자들을 가진 배열에 대해서, 각 원소들의 제곱값으로 새로운 배열을 생성하는 방식은... [ i**2 for i in scaleRange ] 와 같습니다.
나머지는 쉽게 이해할 수 있습니다. 이렇게 해도 일단 단일수의 100까지는 충분한 듯 싶습니다.
2. Unlimited
to be continue.... (라고 쓰고 돌아오기까지 시간이 좀 걸렸네요...)
이제는 제약조건을 두어 Test case가 10000개의 Test case에 최대 10000까지 구하기 (time out 발생가능)를 수행해 보겠습니다. 실제로 max를 max번 돌리면... 상당히 오랜 시간이 걸립니다.
그래서 생각한것은 아래의 2가지를 추가하는 것입니다.
- memoization을 통해서 주기적으로 반복되는 값을 사전에 저장
- 1~n 까지의 합의 제곱을 구할때 sum( )조차도 오래 걸릴 수 있으니 최적화
사실 매번 1^2, 2^2 .... n^2까지 구한다면, 비효율 적이라고 할 수 있습니다. 따라서 처음에 Test case를 받기전에 1부터 10000까지의 제곱의 합을 순차적으로 구해 Stack에 저장해 놓는 방법입니다. 그럼 다음의 Test case부터는 목표값의 위치에 접근해서 그냥 값을 가져오는 것이지요.
def preCalc(target):
res = []
res.append(0)
res.append(1)
for i in range(2,target+1):
res.append(res[i-1]+i**2)
return res
두번째는, sum( )마저도 수학적인 공식으로 최적화 한다. 순차적인 합은 사실 첫값 + 끝값의 반복이라고 할 수 있습니다. 예를들어, 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10의 경우...... 첫값 + 끝값 = 11이 5번 반복되었습니다. 이를 코드로 표현하면...
def calcSumSquare(target):
res = (target+1) * (target//2)
if target%2: res += target//2 + 1
return res**2
그렇다면 최종적인 코드는 어떻게 될까요??
def preCalc(target):
res = []
res.append(0)
res.append(1)
for i in range(2,target+1):
res.append(res[i-1]+i**2)
return res
def calcSumSquare(target):
res = (target+1) * (target//2)
if target%2: res += target//2 + 1
return res**2
if __name__ == '__main__':
squareSum = preCalc(10000)
tc = int(input())
for i in range(tc):
target = int(input())
print(calcSumSquare(target) - squareSum[target])말 그대로... 처음에 squareSum이라는 list에 preCalc로 누적된 제곱의 합을 저장하고... 실제 loop에서는 입력된 값의 위치에서 단지 꺼내와서 연산만 하는 방식입니다.
이렇게 하니... 시간이 획기적으로 단축되네요~^ ^
-Ayotera Lab-
댓글