1003: 피보나치 count

• 피보나치를 재귀를 활용하면 2^n이지만 dp를 사용하면 o(n)에 끝낼 수 있다
  -> 재귀를 하나 들어갈때마다 값이 결정된다.
  재귀를 n번들어가면 n개의 값이 결정되고, 그렇기때문에 o(n)에 풀수있다
  이 문제는 2^40이 되면 시간초과가 나기때문에 dp를 사용해야한다

import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.Arrays;

public class Main{
    static int fibo[];
    //40이하이므로 41까지
    static final int MAX_SIZE=41;
    //dp를활용한 피보나치
    public static int fibonacci(int n){
        //내가 memo해놓은 값이라면 더이상 재귀호출을 하지 않고 값을 return한다
        if(fibo[n]!=-1) {
            return fibo[n];
        }
        //memo를 해야 다음번에 이값을 활용한다
        fibo[n] = fibonacci(n-1) + fibonacci(n-2);
        return fibo[n];
    }
    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 n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        fibo = new int[MAX_SIZE];
        for(int i=0;i<fibo.length;i++){
            fibo[i] = -1;
        }
        //여러번의 계산이 들어올수있으니 그냥 차라리 최댓값에 대해 미리구해놓고 배열을 참조한다
        //기본값을 함수들어갈때마다 세팅하는게 아니라 일단 여기서 세팅해주고 fibonacci를 호출했을땐 함수안에 값이 있으므로 
        fibo[0] = 0;
        fibo[1] = 1;
        fibonacci(MAX_SIZE-1);
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(br.readLine());
            //기본값은 정해져잇는값들을 출력한다. 이 기본값들은 else문에서 사용하는 조건으로는 제대로 출력이 안되기때문이다
            if(arr[i]==0) bw.write("1 0\n");
            else if(arr[i]==1) bw.write("0 1\n");
            //0이 나오는 개수와 1이나오는개수를 나열해보았다. 그래봤더니 일정한 규칙이있는것을알게되었다
            //0이 나오는 개수는 입력받은 수-1에 대한 피보나치값이라는것을알았고
            //1이나오는개수는 입력받은수에 대한 피보나치값이라는것을알게되었다.
            //기록된값을 그냥 return하기만한다. 그렇기때문에 fibonacci(max)에서의 시간복잡도만신경쓰면된다
            else bw.write(fibo[arr[i]-1] + " " +fibo[arr[i]] + "\n");
        }
        bw.flush();
        bw.close();
    }


}

1912: 연속합

import java.io.*;
import java.lang.reflect.Array;
import java.nio.Buffer;
import java.util.ArrayList;
import java.util.Arrays;

public class Main{
    public static int solve(int arr[]){
        //이전값에서의 가장큰값 vs 지금내가 바라보고있는곳에서의 최대값을 항상 비교
        //dp[idx]는 idx라는 위치에서의 최댓값을 의미한다
        int dp[] = new int[arr.length];
        //가장작은값을 넣어주는것도 좋지만 arr[0]와같이 첫번째값을 넣어주는것도 좋다
        //그 수안에서어차피 비교될대상이기때문에
        int max = arr[0];
        //arr[0]까지의 가장큰수는 일단 자신일것이다
        dp[0] = arr[0];
        //arr[0]의값은 넣어줬으니 부터시작한다
        for(int i=1;i<arr.length;i++){
            //가장바로전값의 최대합 + 지금나의값 vs 지금나의값 하나만
            //비교하여 현재i에서의 가장 최대값을 구한다
            //max는 지금껏의 max들과 비교한다
            dp[i] = Math.max(dp[i-1]+arr[i], arr[i]);
            max = Math.max(dp[i], max);
        }
        return max;
    }
    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 n = Integer.parseInt(br.readLine());
        int arr[] = new int[n];
        String input[] = br.readLine().split(" ");
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(input[i]);
        }
        bw.write(solve(arr)+"");
        bw.flush();
        bw.close();
    }


}