백준 1309(동물원) - Python(파이썬),Java(자바) - 다이나믹

1309번: 동물원

dp[ i ] : i번째에 사자가 있는 경우의 가지 수

array[ i ] : 2*i 배열에서 사자의 경우의 수

 

ex ]

i= 4인 경우 -> 4번째에 사자가 있는 경우의 가지 수를 의미

① 3( 4-1 ) 번째에 사자가 있는 경우 ( dp[3] ) -> 밑에 그림고 같이 4번째에 사자의 자리는 무조건 정해질 수 밖에 없다 

  => 경우의 수 :  dp[3] * 1 ( 사자 자리 지정 되므로 ) 

i=1	i=2	i=3	i=4
		O
			O

i=1	i=2	i=3	i=4
			O
		O

② 3번째에 사자가 없는 경우의 수 ( array[ 2] : 2*2 배열에서 사자의 경우의 수를 의미 )

     -> 이 경우에는 3번째에 사자가 없으므로 4번째에 사자의 자리는 어디든 와도 상관이 없다

   => 경우의 수 : array[2] * 2

i=1	i=2	i=3	i=4
			O
			O

 

즉, 4번째에 사자가 있는 경우의 수 dp[4] = dp[3]*1 + array[2] *2 

그리고 2*4 배열의 사자의 총 경우의 수 =. 2*3배열의 사자의 총 경우의 수 + i=4번째에 사자가 올 경우의 수 이므로 

2*4 배열의 사자의 총 경우의 수 array[4] = array[3] + dp[4] 

---

따라서 점화식은

  dp[i] = dp[i-1]*1 + array[i-2]*2( 단, i>= 2인 경우 ) , array[ i ] = array[i-1]+dp[i] ( 단, i>=1인 경우 ) 

  i = 0인 경우 , 사자가 아예 없을 때도 경우의 수라고 하였으므로 dp[0] =1 , array[ 0 ] = 1

  i =1 인 경우 , dp[1] =2, array[1] = array[ 0 ]+dp[1] = 3

풀이방법
① 리스트 개수가 N만큼 dp,array 리스트 선언 
② i>1인 경우 dp[ i ] = dp[i-1] *1 + array[i-2]*2 , array[ i ] = array[ i-1 ] + dp[i]
③ i = 0인 경우, dp[0] =array[0]=1
     i=1인 경우, dp[1] = 2, array[1]= 3 대입
④ 단, 숫자가 매우 커지기 때문에 9901로 나눈 나머지를 구해야하므로 array에 계산할 때 9901의 나머지 값이 들어가야한다.
즉, 점화식을 array[ i ] = ( array[ i-1 ] + dp[i] ) % 9901 로 변경

Pytho의 경우 (파이썬) 

import sys
N = int(sys.stdin.readline())
#dp ,array 리스트 선언
dp=[0]*(N+1)
#사자를 배치하는 경우의 수
array=[0]*(N+1)

#n=0인 경우 초기화
dp[0]=array[0]=1
if N>0:#n=1인 경우 초기화
    dp[1]=2
    array[1]=3
if N>1:#n은 2이상의 경우
    for i in range(2,N+1):
        dp[i]=dp[i-1]+array[i-2]*2
        array[i]=(array[i-1]+dp[i])%9901

print(array[N])

Java의 경우 (자바)

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] array= new int[N+1];
        int[] dp = new int[N+1];
        dp[0]=array[0]=1;
        if(N>0){
            dp[1]=2;
            array[1]=3;
        }
        if(N>1){
            for(int i=2;i<N+1;i++){
                dp[i]=dp[i-1]+array[i-2]*2;
                array[i]=(array[i-1]+dp[i])%9901;
            }
        }
        System.out.println(array[N]);
    }
}