๋ฐ์ํ
๋ชฉ์ฐจ
https://www.acmicpc.net/problem/9095
๋ฌธ์ ํ์ด
์๊ฐ์ ํ์ด 1์ด์ด๋ฏ๋ก ์ผ๋ฐ์ ์ธ for๋ฌธ์ ์ฌ์ฉํ ์ ์๋ค. DP๋ก ํ์ด๋ณด๊ฒ ๋ค.
์ ์ n์ ์์์ด๋ฉฐ 11๋ณด๋ค ์๋ค. 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด์ผํ๋ค.
[0]~[10]์ธ ๋ฐฐ์ด์ ์์ฑํ๋ค๊ณ ํ์. [0]์ ์ฌ์ฉํ์ง ์๋๋ค.
์ ์ดํด๋ณด๋ฉด
[2]๋ [1]์ +1์ ๋ํ๊ฐ๊ณผ ์๊ธฐ์์ ์ธ 2๋ฅผ ๊ฐ์ง๊ณ ์๊ณ
[3]์ [2]์ +1์ ๋ํ๊ฐ๊ณผ ์๊ธฐ์์ ์ธ 3์ ๊ฐ์ง๊ณ ์๋ค.
[4]๋ [3]+1, [2]+2, [1]+3์ ๋ํ๊ฐ์ ๊ฐ์ง๊ณ ์์ง๋ง ์๊ธฐ์์ ์ธ "4"๋ ํํํ ์ ์๊ธฐ ๋๋ฌธ์ ์ ์ธ๋์๋ค.
[5]๋ [4]+1, [3]+2, [2]+3, [1]+4๋ก ํํํ ์ ์์ง๋ง "4"๋ ๊ตฌ์ฑ์์์ธ 1, 2, 3์ด ์๋๊ธฐ๋๋ฌธ์ ์ ์ธ๋์๋ค.
์ ์ถ์ฝ๋
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int[] nums = new int[11];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
nums[0] = 0;
nums[1] = 1;
nums[2] = 2;
nums[3] = 4;
//๋ฐฐ์ด ๊ฐ ์
ํ
for (int i = 4; i <= 10; i++) {
nums[i] = nums[i-3] + nums[i-2] + nums[i-1];
}
//์ถ๋ ฅ
for (int t = 0; t < T; t++) {
int n = Integer.parseInt(br.readLine());
System.out.println(nums[n]);
}
}
}
๋ฐ์ํ
'๐ฏ Coding Test' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[๋ฐฑ์ค] 1932๋ฒ ์ ์ ์ผ๊ฐํ ์๋ฐ DP (0) | 2022.04.04 |
---|---|
[๋ฐฑ์ค] 1074๋ฒ Z ์๋ฐ (๋ถํ ์ ๋ณต) (0) | 2022.02.24 |
[๋ฐฑ์ค] 2630๋ฒ ์์ข ์ด ๋ง๋ค๊ธฐ ์๋ฐ (๋ถํ ์ ๋ณต) (0) | 2022.02.22 |
[๋ฐฑ์ค] 1012 ์ ๊ธฐ๋๋ฐฐ์ถ ์๋ฐ BFS, DFS (0) | 2022.02.21 |
[๋ฐฑ์ค] 1697 ์จ๋ฐ๊ผญ์ง 1์ฐจ์ BFS (0) | 2022.02.12 |