[Python] Mortal Fibonacci Rabbits

안녕하세요!

 

오늘은 새로운 문제를 풀어보도록 하겠습니다!

 

저번에 풀었던 문제중에 피보나치 관련 문제가 있었습니다. 그거랑 비슷한 문제를 보게되어 풀었던 방법을 올려보도록 하겠습니다.

 

저번 문제는 다음 링크로 가시면 되고, 

 

mopipe.tistory.com/73

Rabbits and Recurrence Relations

 

이번문제는 저번문제와 내용은 같으나 추가되는 조건이 있습니다. 토끼에 수명을 추가로 하는것이죠!

 

저번문제는 토끼가 Immportal하게 살아있다라는 가정하게 진행이 된것이고, 이번문제는 토끼에 수명을 추가로 하는것이죠.

 

고민 많이 했습니다. 조금 어렵더라구요!

 

주어진 값들은 : n <=100, m <= 20 이고,

 

받아야하는 값들은 : n개월후에 토끼의 수입니다. 토끼의 수명은 m개월이라고 가정을 하는것이죠.

 

예시로, n=6, m=3이 나왔습니다. (결과값은 4!)

 

저번처럼 표를 만들어 보았습니다.

 

개월	1	2	3	4	5	6
생식가능	0	1	1	1	2	2
생식불가	1	0	1	1	1	2
총마리수	1	1	2	2	3	4

 

표를 그리면서 또 헷깔렸는데, 이번 문제는 확실히 뭔가 더 복잡한 것 같습니다.

 

그래서 차원수를 늘려서 확인을 해보았습니다.

 

토끼의 수명이 3개월이기 때문에, 아기,성인,노인 이렇게 세가지로 나누어서 진행을 해보았고, 개월수를 늘려보았습니다.

 

개월	1	2	3	4	5	6	7	8	9
아기	1	0	1	1	1	2	2	3	4
성인	0	1	0	1	1	1	2	2	3
노인	0	0	1	0	1	1	1	2	2
총 마리수	1	1	2	2	3	4	5	7	11

 

 보시면 무엇인가 패턴이 조금 보이는 것 같습니다. (저는 한번 풀었기 때문에 한번에 보입니다.) 어떤것이냐.

 

표를 이용해서 총 마리수를 구하는 식을 만들어보겠습니다. 

 

개월	1	2	3	4	5	6	7	8	9
input 1	1	0	Fn-1 (2)	Fn-2 (2)	Fn-2 (3)	Fn-2 (4)	Fn-2 (5)	Fn-2 (6)	Fn-2 (7)
input 2	0	1	Fn-2 (1)	Fn-3 (1)	Fn-3 (2)	Fn-3 (3)	Fn-3 (4)	Fn-3 (5)	Fn-3 (6)
총 마리수	1	1	2	2	3	4	5	7	11

 

위 표에서 괄호는 Input개월 총 마리수를 넣은 것입니다.

 

1,2 개월까지는 첫 시작단계인 1마리가 성장하는 과정이고, 3개월의 경우는 피보나치 순열이 적용되고, 

 

그 이후부터 새로운 피보나치가 적용됩니다. 그러나 우리가 토끼의 수명이 m개월이기 때문에 m개월의 수명에 따라 식적용이 달라질 수도 있기 때문에 확실하게 확인해봐야겠죠.

 

m은 5라고 생각하고 표를 만들어보겠습니다.

 

개월	1	2	3	4	5	6	7	8	9
유아기	1	0	1	1	2	3	4	7	10
청소년기	0	1	0	1	1	2	3	4	7
성인기	0	0	1	0	1	1	2	3	4
노인기	0	0	0	1	0	1	1	2	3
영혼기	0	0	0	0	1	0	1	1	2
총 마리수	1	1	2	3	5	7	11	17	26

 

이것을 다시 총마리를 구하는 식으로 표현하면 다음과 같습니다.

 

개월	1	2	3	4	5	6	7	8	9
input 1	1	0	Fn-1 (2)	Fn-1 (3)	Fn-1 (4)	Fn-2 (4)	Fn-2 (5)	Fn-2 (6)	Fn-2 (7)
input 2	0	1	Fn-2 (1)	Fn-2 (2)	Fn-2 (3)	Fn-3 (3)	Fn-3 (4)	Fn-3 (5)	Fn-3 (6)
input 3	0	0	0	0	0	Fn-4 (2)	Fn-2 (3)	Fn-4 (4)	Fn-4 (5)
input 4	0	0	0	0	0	Fn-5 (1)	Fn-1 (2)	Fn-5 (3)	Fn-5 (4)
총 마리수	1	1	2	3	5	7	11	17	26

 

이 표를 확인하면서 우리가 알 수 있는 점은 

 

 m>3개월일 때, 3개월이상 m개월이하에서는 일반적인 피보나치가 적용되고,

 

 m개월이 넘어가면서 부터 2~m개월 전의 총 마리수를 더하면 값이 나오는 것을 확인할 수가 있었습니다.

 

이것을 이용해서 코드를 만들어보면, 다음과 같습니다.

 

#/usr/bin/env/python

def rabbit(n,m): # n은 개월수, m은 토끼의 수명
	a=1 # 처음 시작 마리수!
    total=[] # 각 개월수마다 값을 추가!
    for i in range(1,n+1): # 개월수로 맞추기 위하여 i에 1에서부터 n개까지 들어감
    	if i in [1,2]:
        	total.append(a)
        if i > 2 and i <= m:
        	value1=total[i-2]+total[i-3] # python은 0이 1이기 때문에 1을 추가로 빼줘야함.
            total.append(value1)
        if i > m:
        	value1=sum(total[i-(m+1):i-2])
            total.append(value1)
    return(total[-1]) # total마지막 변수가 우리가 원하는 결과이기때문

 

위와같이 코드를 만들었습니다. (코드는 간결하고 빠른 좋은 코드가 있을뿐 항상 정답이 없습니다. 새로운 방법이 있으면 댓글로 써주세요!)

 

---

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