[백준] 2193번 (이친수)

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

2193번: 이친수

---

1. 아이디어

주어진 조건을 만족시키며 dp 배열에 저장하기 위해 2차원 배열을 사용. 0으로 끝나는 경우를 dp[i][0], 1로 끝나는 경우를 dp[i][1] 로 나누어 생각함.

• 점화식 :
  • F(n)[0] = F(n-1)[0] + F(n-1)[1]
  • F(n)[1] = F(n-1)[0]
• dp[1][0] = 0, dp[1][1] = 1 
• for문 2부터 N 까지 값 구하여 dp 2차원 배열 저장.
• 1 <= N <= 90 이므로 int의 범위를 벗어남. 따라서 long 사용.

---

2. 코드

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		long[][] dp = new long[n+2][2];
		
		dp[1][0] = 0; 
		dp[1][1] = 1;
		
		for(int i=2; i<=n; i++) {
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			dp[i][1] = dp[i-1][0];
		}
		System.out.println(dp[n][0] + dp[n][1]);
	}
}