[백준 알고리즘] (DP) 2193번 Java 풀이

DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052

출처: https://plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기 [plzrun's algorithm]

 

백준 알고리즘 2193번

 

<풀이> - Bottom up

 

풀이 과정

요즘 다이나믹 프로그래밍 문제들을 풀면서 점화식 구하는 과정이 어려웠는데,

문제들을 다양하게 계속 접하다보니 어느정도 익숙해졌나보다.

조금만 나열을 해보고 규칙을 나름 쉽게 파악했다.

package dp;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class N2193 {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n =Integer.parseInt(br.readLine());
        long dp[][] = new long[91][2];
        br.close();
        
        dp[1][1] = 1;
        dp[2][0] = 1;
        
        for(int i=3;i<n+1;i++) {
            for(int j =0; j<2; j++) {
                if(j==0) {
                    dp[i][j] = dp[i-1][0] + dp[i-1][1];
                }
                else {
                    dp[i][j] = dp[i-1][0];
                }
            }
        }
        
        long sum = dp[n][0] + dp[n][1];
        System.out.println(sum);
    }
 
}