반응형
DP ....,,,,
재귀로 예전에 맞았었는데 재채점 이후 시간초과가 났다.
그래서 DP로 작성했더니 통.과.!
사용된 0과 1의 갯수를 출력하는 문제였기 때문에 나는 0의 배열과 1의 배열을 만들었다.
의 재귀 함수를 DP로 바꾸면 된다.
풀이
1. 피보나치 값이 0과 1일때는 바로 "1 0", "0 1" 로 출력한다.
2. arr[][] 함수를 만들어서 0과 1을 따로 카운트 한다.
3. 현재값은 전의값과 전전값이 합쳐진 값이기 때문에 아래와 같은 방정식이 나오게 된다.
arr[N] = arr[N-1] + arr[N-2]
위의 식을 이용하면 끄읏.
소스
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 | import java.io.BufferedReader; import java.io.FileInputStream; import java.io.InputStreamReader; class Main { static BufferedReader br; public static void main(String[] args) throws Exception { //br = new BufferedReader(new InputStreamReader(System.in)); br = new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"))); int TestCase = Integer.parseInt(br.readLine()); for (int t = 0; t < TestCase; t++) { int n = Integer.parseInt(br.readLine()); int[][] arr = new int[n+1][2]; // 0일때 if(n==0) { System.out.println("1 0"); continue; } // 1일때 if(n==1){ System.out.println("0 1"); continue; } arr[0][0] = 1; arr[1][1] = 1; for(int i=2; i<=n; i++){ arr[i][0] = arr[i-1][0]+arr[i-2][0]; arr[i][1] = arr[i-1][1]+arr[i-2][1]; } System.out.println(arr[n][0]+" "+arr[n][1]); } } } | cs |
반응형
'나는요 공부가 좋....은걸... > 알고리즈음' 카테고리의 다른 글
| [BOJ] 백준 2579 - 계단 오르기 (자바) (0) | 2018.05.03 |
|---|---|
| [BOJ] 백준 1194 - 달이 차오른다, 가자. (자바) (0) | 2018.05.01 |
| [BOJ] 백준 11720 - 숫자의 합 (자바) (0) | 2018.04.26 |
| [BOJ] 백준 15686 - 치킨 배달 (자바) (0) | 2018.04.16 |
| [BOJ] 백준 15683 - 감시 (자바) (4) | 2018.04.16 |