백준 15624번 피보나치 수 7 [Python / JavaScript]

백준 15624번 피보나치 수 7 

문제 유형: DP (동적 계획법)

 

문제 주의할 점

Python, JavaScript로 풀이시 Top-Down 방식 즉, 재귀 방식으로는 시간 초과가 발생한다.

또한 입력으로 주어지는 수가 최대 100만인데, Python은 최대 1000번까지 재귀할 수 있으므로 재귀 방식으로는 풀리지 않는다.

따라서 이 문제는 메모이제이션 + Bottom-Up 방식으로 풀이한다.

 

Python 코드

	inputN = int(input())
	pivoDict = {0:0, 1:1}
	def pivo(idx):
	if idx in pivoDict:
	return pivoDict[idx]
	for n in range(2, idx+1):
	pivoDict[n] = ((pivo(n-1) % 1000000007) + (pivo(n-2) % 1000000007)) % 1000000007
	return pivoDict[idx]
	print(pivo(inputN))

view raw 15624.py hosted with ❤ by GitHub

 

 

JavaScript 코드

	pivoDict = {0:0, 1:1}
	function pivo(idx){
	if(idx in pivoDict){
	return pivoDict[idx]
	}
	else{
	for(let n=2; n<idx+1; n++){
	pivoDict[n] = ((pivo(n-1)%1000000007) + (pivo(n-2) % 1000000007)) % 1000000007
	}
	return pivoDict[idx]
	}
	}
	console.log(pivo(1000))

view raw 15624.js hosted with ❤ by GitHub