백준 10870번 파이썬

문제 링크 : https://www.acmicpc.net/problem/10870

 

구현

num = int(input())
result_list = [];
cnt = 0
def fun (num):
	global cnt
	while True:
		if len(result_list) == 0:
			result_list.append(0)
			cnt += 1
		elif len(result_list) == 1 :
			result_list.append(1)
			cnt += 1
		elif len(result_list) == num + 1:
			cnt += 1
			break;
		else : 
			result_list.append(result_list[len(result_list) - 1] + result_list[len(result_list) - 2])
			cnt += 1
			if len(result_list) == num + 1:
				cnt += 1
				break;
		
fun (num)
print(cnt)

괴랄한 나의코드;;;; 지금봐도 가독성도 느껴지지 않고 최악;;;;;인데 놀랍게도 돌아가긴 함;;;;;;;

 

구현2

num = int(input())
arr = [0, 1]

for i in range(2, num+1):
	arr.append(arr[i-1]+arr[i-2])

print(arr[num])

 

 

 

---

수정한 코드1 (반복문 활용)

num = int(input())

arr = [-1] * (num + 2)
arr[0], arr[1] = 0, 1

for i in range(2, num+1):
	arr[i] = arr[i-1] + arr[i-2]

print(arr[num])

• 반복문 만을 활용하여 수정함.

 

[설명]

1. 일단 빈 입력받은 Num의 수만큼 arr을 만들어주는데 피보나치 수열에서 나올 수 없는 -1을 담은 배열을 만들어 주는 것이 포인트. (값이 들어갔는지 안들어 갔는지 확인할 때 필요함)
2. 근데 왜 Num + 1 이 아니라 2 인가요?
   • 만약 입력값 Num이 0 일 경우, 0을 곱하는 거라서 에러가 남. 그래서 배열이 만들어지지 않을 수 있기 때문에 안전하게 + 2를 해준다.
3. 그리고, 배열의 0번째와 1번째는 0과 1이 들어간다고 했으니 넣어줌.
4. 그 다음에 For문을 활용해서 배열에 피보나치 수열 형태의 값을 담아주면 됨.

 

 

---

수정한 코드2 (재귀함수 활용)

def fun(num):

	if num == 0:
		return 0
	if num == 1:
		return 1

	return fun(num - 1) + fun(num - 2)

num = int(input())
print(fun(num))

• 재귀 함수를 활용한 코드

[설명]

1. 입력값이 0이거나 1이면 각각 0, 1을 리턴함.
2. 그게 아닐 경우 피보나치 수열을 만들어 줘야 하는데 발 그림을 이용하자면 아래와 같은 형태로 만들어진다. 그러면 항상 수의 -2, -1 패턴이 만들어 지는데 이 부분을 재귀함수로 구현해줌.

 

---

 

수정한 코드3 (재귀함수 활용2)

def fun(num):
	global arr
	if arr[num] != -1:
		return arr[num]

	arr[num] = fun(num-1) + fun(num-2)
	return arr[num]

num = int(input())
arr = [-1] * (num+2)
arr[0], arr[1] = 0, 1
print(fun(num))

• 재귀함수 활용한 2번째 코드를 수정해본다. 왜? 저렇게 하면 아래와 같이 중복 체크하는 것들이 많아져서 복잡도가 커짐. 그럼 재귀함수를 활용하되, 이 부분의 중복 체크를 줄여보자.

 

1. Num을 입력받고 -1로 이뤄진 배열을 만든다음에 0,1번째에 0,1을 넣는다 (여기까진 1번과 동일하다)
2. 먼저 배열에 -1 이 있는지 없는지 (배열이 비였는지 안비었는지) 확인함.