๋ฌธ์
๋ฌธ์ ๋งํฌ https://www.acmicpc.net/problem/1003
- ๋ค์ ์์ค๋ N๋ฒ์งธ ํผ๋ณด๋์น ์๋ฅผ ๊ตฌํ๋ C++ ํจ์์ด๋ค.fibonacci(3)์ ํธ์ถํ๋ฉด ๋ค์๊ณผ ๊ฐ์ ์ผ์ด ์ผ์ด๋๋ค.
int fibonacci(int n) {
if (n == 0) {
printf("0");
return 0;
}
else if (n == 1) {
printf("1");
return 1;
}
else {
return fibonacci(nโ1) + fibonacci(nโ2);
}
}
- fibonacci(3)์ fibonacci(2)์ fibonacci(1) (์ฒซ ๋ฒ์งธ ํธ์ถ)์ ํธ์ถํ๋ค.
- fibonacci(2)๋ fibonacci(1) (๋ ๋ฒ์งธ ํธ์ถ)๊ณผ fibonacci(0)์ ํธ์ถํ๋ค.
- ๋ ๋ฒ์งธ ํธ์ถํ fibonacci(1)์ 1์ ์ถ๋ ฅํ๊ณ 1์ ๋ฆฌํดํ๋ค.
- fibonacci(0)์ 0์ ์ถ๋ ฅํ๊ณ , 0์ ๋ฆฌํดํ๋ค.
- fibonacci(2)๋ fibonacci(1)๊ณผ fibonacci(0)์ ๊ฒฐ๊ณผ๋ฅผ ์ป๊ณ , 1์ ๋ฆฌํดํ๋ค.
- ์ฒซ ๋ฒ์งธ ํธ์ถํ fibonacci(1)์ 1์ ์ถ๋ ฅํ๊ณ , 1์ ๋ฆฌํดํ๋ค.
- fibonacci(3)์ fibonacci(2)์ fibonacci(1)์ ๊ฒฐ๊ณผ๋ฅผ ์ป๊ณ , 2๋ฅผ ๋ฆฌํดํ๋ค.
- 1์ 2๋ฒ ์ถ๋ ฅ๋๊ณ , 0์ 1๋ฒ ์ถ๋ ฅ๋๋ค. N์ด ์ฃผ์ด์ก์ ๋, fibonacci(N)์ ํธ์ถํ์ ๋, 0๊ณผ 1์ด ๊ฐ๊ฐ ๋ช ๋ฒ ์ถ๋ ฅ๋๋์ง ๊ตฌํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
- ์ฒซ์งธ ์ค์ ํ ์คํธ ์ผ์ด์ค์ ๊ฐ์ T๊ฐ ์ฃผ์ด์ง๋ค.
- ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ ํ ์ค๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ , N์ด ์ฃผ์ด์ง๋ค. N์ 40๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์ฐ์ ๋๋ 0์ด๋ค.
- ๊ฐ ํ ์คํธ ์ผ์ด์ค๋ง๋ค 0์ด ์ถ๋ ฅ๋๋ ํ์์ 1์ด ์ถ๋ ฅ๋๋ ํ์๋ฅผ ๊ณต๋ฐฑ์ผ๋ก ๊ตฌ๋ถํด์ ์ถ๋ ฅํ๋ค.
์์ด๋์ด
- ๋ฌธ์ ๋ฅผ ๋ณด๊ณ dp๋ก ํ์ด์ผ๋๋ ๋ฌธ์ ๋ผ๊ณ ์๊ฐํ๋ค.
- ํฐ ์ซ์๋ฅผ ์์ ์ซ์๋ค์ ๊ฒฐ๊ณผ๊ฐ์ผ๋ก ์ ์ถํ๋ ์ํฅ์์ผ๋ก ํ์ด์ผ๊ฒ ๋ค๊ณ ์๊ฐํ๋ค.
๊ฒช์ ์ํ์ฐฉ์ค
- ์ฒ์์ 'dp๊ฐ ์ด๋ ๊ฒ ํธ๋๊ฒ ๋ง๋?', 'ํน์ ์๊ฐ์ด๊ณผ๋์ง ์์๊น?'๋ผ๋ ์๊ฐ์ ํ์ง๋ง ๋คํํ ์๊ฐ์ด๊ณผ๋์ง ์๊ณ ๋ง์ถ ์ ์์๋ค.
- dp์ ๊ดํด์ ๊ณต๋ถ๋ฅผ ์ข ๋ ํด๋ด์ผ๊ฒ ๋ค..!
์ฝ๋
import java.io.*;
import java.util.*;
public class BOJ1003 {
static int fibo[][];
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());
fibo = new int[N + 1][2];
// 0์ ํผ๋ณด๋์น ์ ๊ฒฐ๊ณผ๊ฐ
fibo[0][0] = 1;
fibo[0][1] = 0;
// N๊ฐ์ด 0๋ณด๋ค ํด๋ ํจ์๋ฅผ ๋๋ฆผ
if(N > 0){
dp(N);
}
sb.append(fibo[N][0] + " " + fibo[N][1] + "\n");
}
System.out.println(sb);
}
public static void dp(int n){
// 1์ ํผ๋ณด๋์น ์ ๊ฒฐ๊ณผ๊ฐ
fibo[1][0] = 0;
fibo[1][1] = 1;
// ์
๋ ฅ๋ฐ์ ์๊น์ง ๋ฐ๋ณต๋ฌธ์ ์ด์ฉํ์ฌ
// ํ์๊ฐ์ผ๋ก ์์๊ฐ์ ์ ์ถ
for(int i = 2; i <= n; i++){
// ํผ๋ณด๋์น ์
fibo[i][0] = fibo[i - 1][0] + fibo[i - 2][0];
fibo[i][1] = fibo[i - 1][1] + fibo[i - 2][1];
}
}
}
'์๊ณ ๋ฆฌ์ฆ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Java] BOJ 2579 ๊ณ๋จ ์ค๋ฅด๊ธฐ (0) | 2024.07.27 |
---|---|
[Java] BOJ 1463 1๋ก ๋ง๋ค๊ธฐ (2) | 2024.07.27 |
[Java] BOJ 17219 ๋น๋ฐ๋ฒํธ ์ฐพ๊ธฐ (6) | 2024.07.24 |
[Java] BOJ 11399 ATM (2) | 2024.07.23 |
[Java] BOJ 11047 ๋์ 0 (2) | 2024.07.23 |