728x90
๐๋ฌธ์ ๋งํฌ
15989๋ฒ: 1, 2, 3 ๋ํ๊ธฐ 4
์ ์ 4๋ฅผ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์ด 4๊ฐ์ง๊ฐ ์๋ค. ํฉ์ ๋ํ๋ผ ๋๋ ์๋ฅผ 1๊ฐ ์ด์ ์ฌ์ฉํด์ผ ํ๋ค. ํฉ์ ์ด๋ฃจ๊ณ ์๋ ์์ ์์๋ง ๋ค๋ฅธ ๊ฒ์ ๊ฐ์ ๊ฒ์ผ๋ก ์น๋ค. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
๐ป์ฝ๋
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][] dp = new int[100001][3];
dp[1][0] = dp[2][0] = dp[2][1] = dp[3][0] = dp[3][1] = dp[3][2] = 1;
for (int i = 4; i < 100001; i++) {
dp[i][0] = dp[i-1][0]; // ...+1๋ก ๋๋๋ ๊ฒฝ์ฐ
dp[i][1] = dp[i-2][0] + dp[i-2][1]; // ...+2๋ก ๋๋๋ ๊ฒฝ์ฐ
dp[i][2] = dp[i-3][0] + dp[i-3][1] + dp[i-3][2];// ...+3๋ก ๋๋๋ ๊ฒฝ์ฐ
}
int t = Integer.parseInt(br.readLine());
StringBuffer sb = new StringBuffer();
for (int i = 0; i < t; i++) {
int n = Integer.parseInt(br.readLine());
sb.append(dp[n][0]+dp[n][1]+dp[n][2]).append("\\n");
}
System.out.print(sb);
}
}
โณํ๊ณ
- ์ค๋ณต์ ์ ๊ฑฐํ๊ธฐ ์ํด์ ์ซ์๊ฐ ์ค๋ฆ์ฐจ์์ผ๋ก ๊ตฌ์ฑ๋๋๋ก ํ์๊ณ , ๊ฒฝ์ฐ๋ฅผ 3๊ฐ์ง๋ก ๋๋์๋ค.
728x90
'Algorithm > Baekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Algorithm/Baekjoon] ๋น๋ฌผ - 14719 (G5/JAVA) (0) | 2023.07.25 |
---|---|
[Algorithm/Baekjoon] ํฌ๋ก์ค ์ปจํธ๋ฆฌ - 9017 (S4/JAVA) (1) | 2023.07.24 |
[Algorithm/Baekjoon] ๋ฑ์ ๊ตฌํ๊ธฐ - 1205 (S4/JAVA) (0) | 2023.07.18 |
[Algorithm/Baekjoon] ๋ง๋ฒ์ฌ ์์ด์ ํ์ด์ด๋ณผ - 20056 (G4/JAVA) (1) | 2023.07.17 |
[Algorithm/Baekjoon] ํ๋์์ ๋ณ๋ฅ๋ณ์ด ๋น๋ฐ์น๋ค - 14658 (G3/JAVA) (1) | 2023.07.11 |