U E D R , A S I H C RSS

최소정수�합/임��

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)


나한테 할 �

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:31:17
Processing time 0.0054 sec