motivation ¶
몇명을 제외하곤 다들 루프를 ㅤㅆㅓㅅ을것 같아 다른 방법을 생각해보았다. 내 코드를 다 짜고보니 현태와 보창이가 가우스의 방법을 써서 summation 을 구한걸 볼 수 있었다. 고등학교 시절을 떠올린 모양이었다. 난 조금 더 시간을 거슬러 올라가 중학교 시절로 올라갔다. 문제에서 요구하는게, ~~이상인 최소 정수(사실 이 문제에서는 범위가 정수가 아닌 자연수로 제한되어 있다고 보는게 더 정확하다)를 구하라인데, 이를 보고 불현듯 부등식이 생각나 바로 적용하였다. 처음에는 DivideAndConquer 를 생각해 보기도 했는데 영 시원치가 않았다가 발상의 전환을 이룬게 도움이 되었다.
시간복잡도는 O(1) 이다. 호호호
시간복잡도는 O(1) 이다. 호호호
코 드 ¶
~cpp
import unittest
import math
def summation(num):
return num*(num+1)/2
def eq_2(a,b,c):
_2a = 2*a
_b_4ac = math.sqrt(b*b-4*a*c)
hae1 = (-b + _b_4ac) / _2a
hae2 = (-b - _b_4ac) / _2a
return hae1, hae2
def minint(num):
hae1, hae2 = eq_2(1.0, 1.0, (float)(-2*num))
hae = (int)(max(hae1, hae2))
sum = summation(hae)
if( sum < num ):
return hae+1, summation(hae+1)
else:
return hae, sum
class TestMinInt(unittest.TestCase):
def testSummation(self):
self.assertEquals(55, summation(10))
self.assertEquals(10, summation(4))
self.assertEquals(5050, summation(100))
self.assertEquals(500500, summation(1000))
if __name__=='__main__':
#unittest.main(argv=('','-v'))
print minint(3000)
