ํผ๋ณด๋์น ์๋ 0๊ณผ 1๋ก ์์ํ๋ค. 0๋ฒ์งธ ํผ๋ณด๋์น ์๋ 0์ด๊ณ , 1๋ฒ์งธ ํผ๋ณด๋์น ์๋ 1์ด๋ค. ๊ทธ ๋ค์ 2๋ฒ์งธ ๋ถํฐ๋ ๋ฐ๋ก ์ ๋ ํผ๋ณด๋์น ์์ ํฉ์ด ๋๋ค.
์ด๋ฅผ ์์ผ๋ก ์จ๋ณด๋ฉด Fn = Fn-1 + Fn-2 (n โฅ 2)๊ฐ ๋๋ค.
n=17์ผ๋ ๊น์ง ํผ๋ณด๋์น ์๋ฅผ ์จ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597
n์ด ์ฃผ์ด์ก์ ๋, n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ n์ด ์ฃผ์ด์ง๋ค. n์ 20๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์ ๋๋ 0์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ n๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ก dp ์ด์ฉํ์ฌ n๋ฒ์งธ ๋์ค๋ ์์ด ๊ตฌํ๊ธฐ
๐ก n์ด 0์ผ ๊ฒฝ์ฐ ๊ณ ๋ คํ๊ธฐ
int[] dp = new int[n + 1];
...
for (int i = 2; i < n + 1; i++)
dp[i] = dp[i - 1] + dp[i - 2];
if (n != 0)
dp[1] = 1;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class DP_13 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int[] dp = new int[n + 1];
if (n != 0)
dp[1] = 1;
for (int i = 2; i < n + 1; i++)
dp[i] = dp[i - 1] + dp[i - 2];
System.out.println(dp[n]);
}
}
์ฑ๊ณตโจ