[백준문제풀이] 2193 이친수 java풀이

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

2193번: 이친수

접근법 : 

**1) 어떻게 풀 것인가?**

dp문제이다

**2) 시간복잡도**

2초로, 넉넉한 편이다. 

**3) 공간복잡도**

128mb인데 n이 90이하이므로 int로 하기엔 부족하고, long으로 해야한다.

**4) 풀면서 놓쳤던점**

dp문제임을 이미 알고 있던 사항인데 뭔가 문제를 풀 생각을 하지 않고 노가다로 풀려고 했다. 

6까지 해봤을때 전 차수보다 +1씩 늘어나길래 아무 생각없이 그렇게 코드를 짰더니 틀렸다.

dp문제가 너무 오랜만이라그런지 어떻게 푸는지 감을 잃었다. 

**5) 이 문제를 통해 얻어갈 것**

어떻게 풀지 논리적으로 생각하고 이를 dp로 풀어나갈것.

 

 

이 문제는 1이 연속으로 오면 안 되므로 

만약 n자리수가 1 이라고 하면 [n-1]은 0이 된다. 그리고 [n-2]는 0이나 1이 될 수 있다. 

만약 n자리수가 0 이라고 하면 [n-1]은 0 혹은 1이 된다. 

그러면 dp[n] = dp[n-1] + dp[n-2]가 된다. (n자리수가 0일 경우와 1일경우의 합)

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());
        long[] dp = new long[91];
        dp[1] = dp[2] = 1;
        if(n ==1 || n ==2){
            System.out.println(dp[n]);
        }
        else{
            for(int i=3; i<=n;i++){
                dp[i] = dp[i-1]+dp[i-2];
            }
            System.out.println(dp[n]);
        }
    }
}