๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/9095
- ์ ์ 4๋ฅผ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์ด 7๊ฐ์ง๊ฐ ์๋ค. ํฉ์ ๋ํ๋ผ ๋๋ ์๋ฅผ 1๊ฐ ์ด์ ์ฌ์ฉํด์ผ ํ๋ค.
- 1+1+1+1
- 1+1+2
- 1+2+1
- 2+1+1
- 2+2
- 1+3
- 3+1
- ์ ์ n์ด ์ฃผ์ด์ก์ ๋, n์ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค.
- ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , ์ ์ n์ด ์ฃผ์ด์ง๋ค. n์ ์์์ด๋ฉฐ 11๋ณด๋ค ์๋ค.
- ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค, n์ 1, 2, 3์ ํฉ์ผ๋ก ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ ์๋ฅผ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ์ฐ์ฐ์ ๊ฐ์๋ฅผ ์ ์ฅํ๋ ๋ฐฐ์ด์ n + 1 ํฌ๊ธฐ๋ก ๋ง๋ค๊ณ 1์ 1, 2๋ 2, 3์ 4๋ก ์ด๊ธฐ๊ฐ์ ์ ์ฅํด์ค๋ค.
- ์ฐ์ฐ์ ๊ฐ์๊ฐ ๋์ด๋๋ ๊ท์น์ ์ฐพ์๋ดค์ ๋, i๋ฒ์งธ ์ฐ์ฐ์ ๊ฐ์๋ i - 1๋ฒ์งธ, i - 2๋ฒ์งธ, i - 3๋ฒ์งธ ์ฐ์ฐ์ ๊ฐ์๋ฅผ ๋ชจ๋ ๋ํ ๊ฐ์ด๋ฏ๋ก N์ด 4์ด์์ด๋ฉด, 4๋ถํฐ N๊น์ง ๋ฐ๋ณต๋ฌธ์ ๋๋ฉด์ ์ ์์ผ๋ก i๋ฒ์งธ ๊ฐ์ ๊ตฌํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- X
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ9095 {
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
// ํ
์คํธ์ผ์ด์ค ๊ฐ์
int T = Integer.parseInt(br.readLine());
for(int test = 0; test < T; test++){
int n = Integer.parseInt(br.readLine());
// ๋ฐฐ์ด์ ํฉ์ ๊ฐ์ ์ ์ฅ
int arr[] = new int[n + 1];
// ๋ฐฐ์ด์ ์ด๊ธฐ๊ฐ์ ์ ์ฅ
// 1์ 1, 2๋ 2, 3์ 4๋ก ์ด๊ธฐ๊ฐ ์ ์ฅ
arr[1] = 1;
if(n > 1){
arr[2] = 2;
}
if(n > 2){
arr[3] = 4;
}
// 4๋ถํฐ๋ ํฉ์ ๊ฐ์๊ฐ i - 1, i - 2, i - 3๋ฒ์งธ ๊ฐ์
// ๋ชจ๋ ๋ํ ๊ฐ
for(int i = 4; i <= n; i++){
arr[i] = arr[i - 1] + arr[i - 2] + arr[i - 3];
}
sb.append(arr[n] + "\n");
}
System.out.println(sb);
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 9461 ํ๋๋ฐ ์์ด (0) | 2024.07.28 |
---|---|
[Java] BOJ 9375 ํจ์ ์ ์ ํด๋น (0) | 2024.07.28 |
[Java] BOJ 2606 ๋ฐ์ด๋ฌ์ค (0) | 2024.07.27 |
[Java] BOJ 2579 ๊ณ๋จ ์ค๋ฅด๊ธฐ (0) | 2024.07.27 |
[Java] BOJ 1463 1๋ก ๋ง๋ค๊ธฐ (2) | 2024.07.27 |