๋ฌธ์
ํด๋น ํฌ์คํ ์ ๋ฐฑ์ค์ 11726๋ฒ 2*n ํ์ผ๋ง ์ ์ ๊ทผ๊ณผ ํด๊ฒฐ ๋ฐฉ๋ฒ์ ์ค๋ช ํ ๊ธ ์ ๋๋ค.
์ ๋ต ์์ค ์ฝ๋๋ฅผ ํ์ธํ์๋ ค๋ฉด solve url ์์ ํ์ธ ๊ฐ๋ฅํฉ๋๋ค.
์ด ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํด ์ด๋ค ๋ฐฉ์์ผ๋ก ์ ๊ทผํด์ผ ํ๋์ง๋ฅผ ๋จผ์ ์๊ฐํด๋ณด์.
ํด๊ฒฐ๋ฒ
2 x n์ ์ง์ฌ๊ฐํ์ ์ฑ์์ผ ํ๋๋ฐ, ์ฐ๋ฆฌ์๊ฒ 2๊ฐ์ง ํ์ผ์ด ์ฃผ์ด์ง๋ค.
- 1 x 2
- 2 x 1
์ด๋ฐ ํ์ผ์ ๊ฐ์ง๊ณ 2 x n ํฌ๊ธฐ์ ํ์ผ์ ์ฑ์์ผ ํ๋ค.
์ ๊ทผ๋ฒ
ํฌ๊ธฐ๊ฐ 2 x n ์ธ ํ์ผ์ด ์์ ๋, ์๋กญ๊ฒ ํ์ผ์ด ์ถ๊ฐ๋๊ธฐ ์ํด์๋ 2๊ฐ์ง ๋ฐฉ๋ฒ๋ง ์กด์ฌํ๋ค.
2 x (n-1)
๋ฒ์งธ ํ์ผ์์ 2 x 1 ํ์ผ์ด ์ถ๊ฐ๋ ๊ฒฝ์ฐ2 x (n-2)
๋ฒ์จฐ ํ์ผ์์ 2 x 2 ํ์ผ์ด ์ถ๊ฐ๋ ๊ฒฝ์ฐ
๊ทธ๋ผ ์ ํ์์ ๋ค์๊ณผ ๊ฐ์ด ์ธ์ธ ์ ์๋ค.
arr[n] = arr[n-1] + arr[n-2];
์ ๋ต ์ฝ๋
import java.io.*;
public class Main {
static int[] memo = new int[1001];
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
bw.write(String.valueOf(dp(n));
}
private static int dp(int n){
if(n == 1 || n == 0) return 1;
if(memo[n] > 0) return memo[n];
memo[n] = dp(n-1) + dp(n-2);
memo[n] %= 10007;
return memo[n];
}
}
๋ฌธ์ ํ๊ณ
DP ๋ฌธ์ ์ ํน์ฑ์ ํ์ ํ๊ธฐ ์ํด์ ์ง๊ธ๊น์ง๋ ์์ผ๋ก ์ฒ์ ๋ถํฐ n ๊น์ง ๊ฐ๋ฉด์ ํน์ฑ์ ์ฐพ์ ๋ ๊น์ง ๋ฐ๋ณตํ์๋ค.
์ง๊ธ๊น์ง ๋ฌธ์ ๋ค์ ์ด๋ ๊ฒ ์ ํ๋ ธ์ง๋ง ์ด๋ฒ ๋ฌธ์ ๋ ๊ทธ๋ ์ง ์์๋ค.
์ด๋ฒ ๋ฌธ์ ๋ n์ผ ๋ ์ด๋ค ํน์ฑ์ ๊ฐ๊ณ ์๋์ง๋ฅผ ํ์
ํ๋ ๊ฒ์ด ์ค์ํ๋ค.
์ด๋ ๊ฒ ์คํฌ ํ๋๊ฐ ๋์์ผ๋ ๋ค์ ๋ฌธ์ ์๋ ์ ์ฉํด๋ณด๋ ค ํ๋ค.
๋๊ธ