백준 24416번 (동적 프로그래밍, 전역변수)

큰 문제를 한 번에 해결하기 어려울 때 재귀 등을 이용해서 작은 문제로 쪼개 해결하게 된다. 그런데 작은 문제들을 풀다보면 같은 문제들을 여러 번 반복해서 풀게 되는 문제점이 발생하는데, 동적 프로그래밍이란 반복되는 문제를 재계산하지 않고 값을 저장해놓고 다시 사용하는 기법을 말한다.

 

처음에는 예시 코드를 그대로 가져와 카운트를 넣어 모두 세보았다.

C언어에서는 '이 x는 전역변수다'라고 선언해놓고 사용한다.

하지만 파이썬에서는 다르다. 외부에서 쓰던 변수x를 함수내에서 global x라고 하면 '그 x는 이 함수내에서만 사용하는 지역변수x가 아닌 전역변수 x다'라는 뜻이다.

 

이런 방식으로 하니 시간초과가 나왔다. 그래서 아예 생각을 바꾸어 하나하나 프로그램을 돌리지 않고 코드1, 2가 몇번 호출될지 간접적으로 구해보려고 했다.

코드 1 : return 1은 사실상 f[n]과 같다. 예를 들어 fib(5) = 5은 return 1을 5번 더해서 만든 것이기 때문이다.

코드 2 : f[i] = f[i-1] + f[i-2]은 3부터 n까지 반복되는 것이므로 n-2와 같다.