매일 Algorithm

백준 9507번

import java.util.Scanner;

public class problem486 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size = in.nextInt();

        for (int i = 0; i < size; i++) {
            int input = in.nextInt();
            System.out.println(fibo(input));
        }

    }

    private static long fibo(int n) {
        if (n < 2) {
            return 1;
        } else if (n == 2) {
            return 2;
        } else if (n == 3) {
            return 4;
        }

        // dp 배열 생성
        long[] koong = new long[n + 1];
        koong[0] = 1;
        koong[1] = 1;
        koong[2] = 2;
        koong[3] = 4;

        for (int i = 4; i <= n; i++) {
            koong[i] = koong[i - 4] + koong[i - 3] + 
            		koong[i - 2] + koong[i -1];
        }
        // 해당 배열 반환
        return koong[n];
    }
}

프로그래머스 (타겟 넘버)

class Solution {
    static int result = 0;
    public int solution(int[] numbers, int target) {
        dfs(numbers, 0, 0, target);
        return result;
    }
    
    private void dfs(int[] numbers, int depth, int sum, int target){
        // 마지막 노드까지 탐색 끝난경우
        // 배열의 길이가 5개이면 경우의수가 32개이다. 2^5
        if(depth == numbers.length){
            if(sum == target){
                result++;
            }
        }else{
            // numbers 배열의 크기만큼 깊이 탐색한다.
            dfs(numbers, depth + 1, sum + numbers[depth], target);
            dfs(numbers, depth + 1, sum - numbers[depth], target);
        }
    }
}