DP 문제풀이-2

피보나치 함수

DP로 피보나치 함수를 풀 때와 비슷하게..
각 값을 배열에 저장하면 된다.
0 과 1의 값을 각각 저장해야하니 2차원 배열을 사용하는 것으로..

0일 때와 1일 때의 값은 주어져있으니
2일 때의 값부터 구해서 배열에 넣어주면 된다

F(n) = F(n-1) + F(n-2)이므로
F(n-1) 일 때 1을 사용하는 횟수, 0을 사용하는 횟수

• F(n-2) 일 때 1을 사용하는 횟수, 0을 사용하는 횟수
  이미 배열에 값이 있는 경우엔 계산을 생략하여 시간을 줄인다.

import java.io.*;

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));

        int[][] fib01 = new int[41][2];
        fib01[0][0] = 1;
        fib01[0][1] = 0;
        fib01[1][0] = 0;
        fib01[1][1] = 1;
        int T = Integer.parseInt(br.readLine());
        for(int i=0;i<T;i++){
            int N= Integer.parseInt(br.readLine());
            for(int j=0;j<=N;j++){
                if(j>=2 && fib01[j][0] == 0){
                    fib01[j][0] = fib01[j-1][0]+fib01[j-2][0];
                    fib01[j][1] = fib01[j-1][1]+fib01[j-2][1];
                }
            }
            bw.write(String.valueOf(fib01[N][0])+" "+String.valueOf(fib01[N][1])+'\n');
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

N번 반복 하면 되므로 시간복잡도 O(n)

1,2,3 더하기

꼼꼼한 계산의 중요성을 알게됨..

1~5까지 하나하나 구해보면
1 => 1개
2 => 2개
3 => 4개
4 => 7개
5 => 13개
6 => 24개(예제에 답이 있음)

규칙을 잘보면
4 => 1+2+4 => 7
5 => 2+4+7 => 13
6 => 4+7+13 => 24

f(n) = f(n-1) + f(n-2) + f(n-3)라는 규칙을 찾을 수 있다.
1~3까지만 하드코딩으로 값을 정해주고 다음 수 부터 값을 찾아 배열에 넣어준다.

꼼꼼하게 계산하면 규칙을 찾을 수도(!) 있었는데 그러질 못해서 해석을 보게 됨..

import java.io.*;

public class solved_9095 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw =new BufferedWriter(new OutputStreamWriter(System.out));

        int T = Integer.parseInt(br.readLine());

        int[] arr = new int[11];
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        arr[3] = 4;
        for(int i = 0;i<T;i++){
            int n= Integer.parseInt(br.readLine());
            for(int j=0;j<=n;j++){
                if(j>3){
                    arr[j] = arr[j-1]+arr[j-2]+arr[j-3];
                }
            }
            bw.write(String.valueOf(arr[n])+"\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }
}

n번 반복하여 구하면 되므로 시간 복잡도 O(n)