0๊ณผ 1๋ก๋ง ์ด๋ฃจ์ด์ง ์๋ฅผ ์ด์ง์๋ผ ํ๋ค. ์ด๋ฌํ ์ด์ง์ ์ค ํน๋ณํ ์ฑ์ง์ ๊ฐ๋ ๊ฒ๋ค์ด ์๋๋ฐ, ์ด๋ค์ ์ด์น์(pinary number)๋ผ ํ๋ค. ์ด์น์๋ ๋ค์์ ์ฑ์ง์ ๋ง์กฑํ๋ค.
์ด์น์๋ 0์ผ๋ก ์์ํ์ง ์๋๋ค.
์ด์น์์์๋ 1์ด ๋ ๋ฒ ์ฐ์์ผ๋ก ๋ํ๋์ง ์๋๋ค. ์ฆ, 11์ ๋ถ๋ถ ๋ฌธ์์ด๋ก ๊ฐ์ง ์๋๋ค.
์๋ฅผ ๋ค๋ฉด 1, 10, 100, 101, 1000, 1001 ๋ฑ์ด ์ด์น์๊ฐ ๋๋ค. ํ์ง๋ง 0010101์ด๋ 101101์ ๊ฐ๊ฐ 1, 2๋ฒ ๊ท์น์ ์๋ฐฐ๋๋ฏ๋ก ์ด์น์๊ฐ ์๋๋ค.
N(1 โค N โค 90)์ด ์ฃผ์ด์ก์ ๋, N์๋ฆฌ ์ด์น์์ ๊ฐ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ N์ด ์ฃผ์ด์ง๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ N์๋ฆฌ ์ด์น์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
๐ก ํ๋์ฉ ๊ตฌํ๋ค ๋ณด๋ฉด ํผ๋ณด๋์น์์ด๊ณผ ๊ฐ๋ค๋ ๊ฒ์ ์๊ฒ ๋จ
๐ก ํผ๋ณด๋์น์์ด ์ด์ฉํด์ ๋ฌธ์ ํด๊ฒฐ
for(int i=2; i<n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class DP_19 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
if(n == 0 || n == 1) {
System.out.println(n);
return;
}
long[] dp = new long[n];
dp[0] = 1;
dp[1] = 1;
for(int i=2; i<n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
System.out.println(dp[n-1]);
}
}
์ฑ๊ณตโจ
long์ ๊ณ ๋ คํด์ ์ง์ผํจ..