[DP] 동물원의 닭

DP 연습문제 : 동물원의 닭

쉬운 DP 문제인데 허점을 찌르는 문제입니다. 적어도 저는 그랬네요. ㅠ

문제

동물원에 한 마리의 닭이 있습니다. 닭 한마리는 하루가 지나면 2마리의 닭을 만듭니다. 닭의 기대 수명은 6일 입니다. 동물원 관리자는 닭들을 위한 사료를 사려고 하는데 얼마만큼 사야하는지 잘 모릅니다. $n$ 일에 몇마리의 닭이 동물원에 있는지 알면 그에 적합한 사료의 양을 계산할 수 있을겁니다. 관리자를 도와주세요. (단, 처음에 한 마리 있는 닭은 $0$ 일에 태어났습니다. )

입력값 :
첫번째 줄은 test case, 두번째 줄 부터는 날짜가 입력됩니다.

출력값 :
$n$ 일 에 해당하는 살아있는 닭의 마리수

제한값 :
$1<=T<=35$
$1<=N<=35$

예시

입력값 :

2
3
7

출력값 :

9
726

설명 :
1일에는 1마리가 있겠죠? 2일에는 1마리가 2마리를 만들어서 총 3마리, 3일에는 3마리가 6마리를 만들어서 총 9마리. 그래서 $n = 3$ 일에는 $9$ 마리가 동물에 있습니다.
계속해서 이런식으로 더하다 보면 $n = 7$ 일이 되는날엔 닭의 수명은 6일 뿐이므로 6일전에 태어난 닭은 죽겠네요. 그 닭은 1마리 이므로, $n=6$ 일날의 닭에서 1 마리가 죽고 나머지 닭들이 2마리씩 또 다른 닭을 만들어 냈으므로, $n = 7$ 일날 총 닭은 $242 + (243-1) *2 = 726$ 입니다.

여기서 먼저 문제를 풀어보세요 !

답

닭이 죽기 시작하기 전날까지는 간단하게 풀 수 있겠습니다.

$n=1$ 일에는 닭이 한마리.
$ n = 2$ 일에는 닭이 $1 + ( 1* 2) = 3$ 마리.
$n=3$ 일에는 닭이 $3 + (3 * 2) = 9$ 마리. $\dotsc$

$n=6$ 일에는 닭이 $81 + (81 * 2) = 243$ 마리.

눈치 채셨나요? $n=i-1$ 일에 있는 닭들의 갯수에 $3$ 을 곱하면 $n = i $ 일에 닭의 개수가 나옵니다.

하지만 $n=7$ 일이 되는순간 꼬이기 시작합니다. 닭이 죽기 시작합니다. $n=7$ 일 기준으로 6일전인 $n=1$ 일에 태어난 닭인 1 마리가 죽습니다. 결국 $n=6$ 일에 살았던 243 마리의 닭중 한마리가 죽어서 242 마리가 되고 $n=7$ 일에 살고있는 닭의 총 마리수는 $242 + (242 * 2)= 726$ 이 됩니다.

$n=8$ 일도 똑같이 계산하시면 됩니다. $n=8-6 =2$ 일에 태어난 닭은 총 $3-1=2$ 마리 이기 때문에 $n=7$ 일에 살았던 726 마리의 닭중 2마리가 죽게되어 724 마리가 되어 $n=8$ 일의 닭의 총 마리수는 $724 + (724 * 2) = 2172 $ 마리가 됩니다.

$n >=7$ 일 부터 닭의 마리수를 계산하실때는 6일전에 태어났던 닭의 마리수를 빼고 계산하시면 됩니다. 중요한점은 이전의 닭의 마리수를 이용하는것이지만, 살아있는 닭이 아니라 태어난 닭의 수를 지워야 한다는 점입니다. 그렇기 때문에 $n$ 일에 태어난 닭을 이전 $n-i$ 일에 살아있는 닭의 마리수로 부터 계산하려면 정말 복잡해 집니다. 다시 말씀드리면, DP 를 이용한 문제이지만 tabulation을 사용할때 배열을 2 개 사용해야된다는 점입니다. '살아있는 닭'과 '태어난 닭' 이렇게 두가지요. 이렇게 하시면 따로 살아있는 닭으로부터 태어난 닭의 마리수를 계산할 필요없이, 그냥 태어난 닭의 마리수를 그때그때 계산해서 저장한뒤에 $6$ 일전에 태어난 닭의 마리수가 궁금하다 싶으면, 저장된 값으로부터 바로 빼내어 쓰면 됩니다.

T = int(input())

#chick[n] : n 일에 살아있는 닭의 갯수
#born[n] : n 일에 태어난 닭의 갯수

chick = [0] * 40
born = [0] * 40

# 0 일에는 태어나지도, 살아있는 닭도 없다. 태초에는 알만 있었다....
chick [0] = 0
born[0] = 0
chick [1] = 1
born[1] = 1

for i in range(2, 40):
    if i <= 6 :		# 이전의 닭의 수를 이용해 계산
        born[i] = chick[i-1] * 2
        chick [i] = chick[i-1] + born [i]
    else :			# 닭이 죽기 시작
        alive = (chick[i-1] - born[i-6])
        born[i] = alive * 2
        chick[i] = alive * 3

for _ in range(T) :
    print (chick[int(input())])

chick list 의 일부분을 출력하여 작성해 보았습니다.

[0, 1, 3, 9, 27, 81, 243, 726, 2172, 6498, 
19440, 58158, 173988, 520512, 1557192, 4658580, 13936860, 41694264, 124734816, 
.... , 15363180201015360, 45961321059052992, 137500374652491264,
411353559774398208, 1230627564228266496]

---

맨처음 이문제를 풀땐 어떻게든 하나의 배열로 해결하려고 안간힘을 썼다가 포기했습니다.

조금 유연성을 기르는 연습을 해야겠습니다.