포스트

피보나치 함수(1003)

게시
By Kim Jung Wook 2 분읽는 시간

피보나치 함수(1003)

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

import java.io.*;
import java.util.*;

public class Main{
    
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int[][] arr = new int[41][2];
    
    arr[0][0] = 1; arr[0][1] = 0; arr[1][0] = 0; arr[1][1] = 1;
    
    for(int i = 2; i < 41; i++){
      arr[i][0] = arr[i-1][0] + arr[i-2][0];
      arr[i][1] = arr[i-1][1] + arr[i-2][1];
    }
    
    int t = Integer.parseInt(br.readLine());
    
    while(t-- > 0){
      int n = Integer.parseInt(br.readLine());
      
      sb.append(arr[n][0]).append(" ").append(arr[n][1]).append("\n");
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
}

풀이과정

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
42
43

import java.io.*;
import java.util.*;

public class Main{
    
  public static int zero = 0;
  public static int one = 0;
  
  public static void main(String[] args) throws IOException{
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringBuilder sb = new StringBuilder();
    
    int n = Integer.parseInt(br.readLine());
    
    while(n-- > 0){
      int num = Integer.parseInt(br.readLine());
      
      fibonacci(num);
      
      sb.append(zero).append(" ").append(one).append("\n");
      zero = 0;
      one = 0;
    }
    
    bw.write(sb.toString());
    bw.flush();
    bw.close();
    br.close();
  }
  
  public static int fibonacci(int n){
    if(n == 0){
      zero++;
      return 0;
    } else if(n == 1){
      one++;
      return 1;
    } else {
      return fibonacci(n-1) + fibonacci(n-2);
    }
  }
}
  1. 처음에는 예제에 나와있는데로 코드를 구현하였다.
  2. 하지만 위의 방식에서는 fibonacci() 메소드를 반복하며 호출하며 값을 추출히기 때문에 시간이 오래걸렸다.
  3. 그래서 n의 값에 따라 0의 갯수와 1의 갯수를 적어보니 0과 1의 갯수가 피보나치 수열을 따른다는 것을 알게 되었다.
  4. 이차배열을 활용하여 문제를 풀었다.
  • 성공
  • 메모리 : 14132 KB
  • 시간 : 116 ms

보안점

  1. 이차배열을 사용하여 풀었는데, 다른 사람의 경우 피보나치 수열, 일차배열을 만들었다.
  2. 입력값 n에 따른 0의 값은 arr[n-1]이고, 1의 값은 arr[n]이기 때문에 일차배열을 이용하여 푼 방식도 있었다.
알고리즘, 문제
알고리즘문제