최소정수의합/임인택

motivation ¶

몇명을 제외하곤 다들 루프를 ㅤㅆㅓㅅ을것 같아 다른 방법을 생각해보았다. 내 코드를 다 짜고보니 현태와 보창이가 가우스의 방법을 써서 summation 을 구한걸 볼 수 있었다. 고등학교 시절을 떠올린 모양이었다. 난 조금 더 시간을 거슬러 올라가 중학교 시절로 올라갔다. 문제에서 요구하는게, ~~이상인 최소 정수(사실 이 문제에서는 범위가 정수가 아닌 자연수로 제한되어 있다고 보는게 더 정확하다)를 구하라인데, 이를 보고 불현듯 부등식이 생각나 바로 적용하였다. 처음에는 DivideAndConquer 를 생각해 보기도 했는데 영 시원치가 않았다가 발상의 전환을 이룬게 도움이 되었다.

시간복잡도는 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)

나한테 할 말 ¶

LittleAOI