[java, 동적 계획법 dynamic programming] 백준2193번 이친수

출처:

https://www.acmicpc.net/problem/2193

2193번: 이친수

 

정답 코드

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        
        int N=sc.nextInt();
        long[] One=new long[N+1];
        long[] Zero=new long[N+1];
    
        One[1]=1;
        Zero[1]=0;
        
        if(N>=2) {
            for(int i=2;i<=N;i++) {
                One[i]=Zero[i-1];
                Zero[i]=One[i-1]+Zero[i-1];
            }
        }
        
        System.out.println(One[N]+Zero[N]);
    }
}

풀이

i자리에 0과 1의 개수

long[] One=new long[N+1];
long[] Zero=new long[N+1];

 

i자리에 올 수 있는 1의 개수

  =  i-1자리에 온 0의 개수

One[i]=Zero[i-1];

Zero[i]=One[i-1]+Zero[i-1];

One[N]+Zero[N];