0%

[백준/2193] 이친수

작성일 Edited on In Disqus:

Baekjoon Online Judge - 2193

Review

example

  • 이미지를 보고 규칙을 찾아보면, 주어진 수가 n일 때 n - 1, n - 2를 해서 원하는 값들을 찾을 수가 있다.
  • 점화식은 이렇다. dp[i] = dp[i - 2] + dp[i - 1]

Code (JAVA)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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[n + 1];

    dp[0] = 0;
    dp[1] = 1;

    for(int i = 2; i <= n; i++) {
      dp[i] = dp[i - 2] + dp[i - 1];
    }

    System.out.println(dp[n]);
  }
}