[Python,rosalind] Rabbits and Recurrence Relations

뭐 쉬운 문제이긴 하지만(난 오래걸림) 겸사겸사 해결한 방법에 대해서 설명하고자 합니다.

 

Fibonacci sequence 는 Fn=Fn-1+Fn-2 로 알려져 있습니다.

 

Wascally Wabbits을 눌러보면 토끼가 1쌍이 자라는데 1달, 생식이 가능(1달후)하면 1쌍의 토끼를 낳을때, 6개월 후면 몇마리가 되느냐?! 라는 예시가 나옵니다. (근친이 일어나서 생식능력이 떨어질 수 있다!!)

 

개월	1	2	3	4	5	6
쌍	1	1	2	3	5	8

 위와 같은 예시가 나옵니다. 그리곤

 

문제는 다음과 같습니다.

 

 주어진것 : n<= 40, k<=5.

 결과물 : n months까지의 토끼의 쌍을 구하고, 시작은 1쌍으로 시작하되, 생식이 가능할 때는 k쌍을 낳는다.

 

Sample Dataset - 5 3 (5개월후에 토끼쌍을 확인해라, 생식이 가능하면 3쌍을 낳는다.

Sample Output - 19 (결과적으로 19쌍이 나와야함)

 

먼저 시험을 풀기 전에  피보나치로 풀어보았지만 당연히 안되었고, 그래서 준비한 것이 각 개월수마다 숫자를 세어보았습니다.

 

 

조금 무식한 방법이지만 다음과 같이 했을때, 5개월 후에는 정확히 19쌍이 나왔습니다.

달	1	2	3	4	5
쌍	1	1	4	7	19

 

그래서 어떻게 n번째 달에 값이 나올까 고민하다가 각 개월마다 생식이 가능한 토끼쌍과, 아닌쌍을 나누어 보았습니다.

 

달	1	2	3	4	5	6
생식가능	0	1	1	4	7	19
생식불가	1	0	3	3	12	21
총 마리수	1	1	4	7	19	40

 

두가지의 그룹으로 나누어보았을 때, 생식 가능한 값들이 Fn-1이라는 것을 확인하였고, 생식불가의 경우 Fn-2 X 3 이라는 것을 확인하였습니다.

 

 

식이 나왔으니, 실제로 맞는지 확인해봐야지요. 그래서 또 무식하게 6번째 달을 그리면서 제가 생각한 식에 대한 결과값과 맞춰보니!

 

맞았습니다!! 그래서 바로 코드를 만들었죠!

 

total=[]
a=1
for i in range(0,5):
	if i<2:
		total.append(a)
	if i>1:
		a=total[i-1]+(total[i-2]*3)
		total.append(a)
		print(a)

 

결과도 잘 나왔고, 또 결과를 쉽게 쓰기 위해서는 함수로 정의하는 것이 나을 것 같아서 함수로 만들었습니다!

 

def rabbit(m,p):
	total=[]
	a=1
	for i in range(0,m):
		if i<2:
			total.append(a)
		if i>1:
			a=total[i-1]+(total[i-2]*p)
			total.append(a)
	return(a)

 

---

이렇게 해서 문제를 해결하였습니다! 아무튼... 문제를 풀고 나면 사람들이 어떻게 풀었는지 다양한 방법들이 나오니 꼭 확인하시구요!

 

---

유용하셨거나, 잘 보셧다면 주변 광고 한번씩만 클릭 부탁드립니다! 감사합니다!