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)