์ค๋ฅธ์ชฝ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ผ๊ฐํ์ด ๋์ ๋ชจ์์ผ๋ก ๋์ฌ์ ธ ์๋ค. ์ฒซ ์ผ๊ฐํ์ ์ ์ผ๊ฐํ์ผ๋ก ๋ณ์ ๊ธธ์ด๋ 1์ด๋ค. ๊ทธ ๋ค์์๋ ๋ค์๊ณผ ๊ฐ์ ๊ณผ์ ์ผ๋ก ์ ์ผ๊ฐํ์ ๊ณ์ ์ถ๊ฐํ๋ค. ๋์ ์์ ๊ฐ์ฅ ๊ธด ๋ณ์ ๊ธธ์ด๋ฅผ k๋ผ ํ์ ๋, ๊ทธ ๋ณ์ ๊ธธ์ด๊ฐ k์ธ ์ ์ผ๊ฐํ์ ์ถ๊ฐํ๋ค.
ํ๋๋ฐ ์์ด P(N)์ ๋์ ์ ์๋ ์ ์ผ๊ฐํ์ ๋ณ์ ๊ธธ์ด์ด๋ค. P(1)๋ถํฐ P(10)๊น์ง ์ฒซ 10๊ฐ ์ซ์๋ 1, 1, 1, 2, 2, 3, 4, 5, 7, 9์ด๋ค.
N์ด ์ฃผ์ด์ก์ ๋, P(N)์ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค. ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , N์ด ์ฃผ์ด์ง๋ค. (1 โค N โค 100)
์ถ๋ ฅ
๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค P(N)์ ์ถ๋ ฅํ๋ค.
์์ ๊ท์น์ฑ๋ง ์ฐพ์ผ๋ฉด ๊ฐ๋จํ ๋ฌธ์
์์ ๊ท์น์ฑ
dp[i] = dp[i-3] + dp[i-2]
import java.io.*;
public class DP_7 {
static long dp[] = new long[101];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
wave();
int tc = Integer.parseInt(br.readLine());
while(tc > 0) {
int n = Integer.parseInt(br.readLine());
System.out.println(dp[n]);
tc--;
}
}
public static void wave() {
dp[1] = 1;
dp[2] = 1;
dp[3] = 1;
for(int i=4; i<101; i++)
dp[i] = dp[i-3]+dp[i-2];
}
}
์ฑ๊ณต~