[백준] 단계별로 풀어보기 > 동적 계획법 1 (java)

+) 풀이 코드

https://github.com/jung0115/CodingTestPractice.git

GitHub - jung0115/CodingTestPractice: Practice Coding Test with Beakjoon, programmers, etc.

 

+) 백준에 Java 코드를 제출할 때는 class명을 Main으로 해주어야 오류가 발생하지 않는다.

 

1003번 - 2022.02.08.화

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
public class Main {
    static Integer[][] fibo = new Integer[41][2];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(bf.readLine());
        int[] test = new int[N];
        for(int i = 0; i < N; i++) {
            test[i] = Integer.parseInt(bf.readLine());
        }
        fibo[0][0] = 1; //0일 때 0 호출 횟수
        fibo[0][1] = 0; //0일 때 1 호출 횟수
        fibo[1][0] = 0; //1일 때 0 호출 횟수
        fibo[1][1] = 1; //1일 때 1 호출 횟수

        StringBuilder printSet = new StringBuilder();
        for(int i = 0; i < N; i++) {
            if(fibo[test[i]][0] == null || fibo[test[i]][1] == null)
                fibonacci(test[i]);
            printSet.append(fibo[test[i]][0]).append(" ").append(fibo[test[i]][1]).append("\n");
        }
        System.out.print(printSet);
    }
    static void fibonacci(int num) {
        if(fibo[num][0] == null || fibo[num][1] == null) {
            fibonacci(num-1);
            fibonacci(num-2);
            fibo[num][0] = fibo[num-1][0] + fibo[num-2][0];
            fibo[num][1] = fibo[num-1][1] + fibo[num-2][1];
        }
    }
}

 

9184번 - 2022.02.15.화

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
    static int[][][] wSet = new int[21][21][21]; //배열 크기가 중요!
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        while(true) {
            StringTokenizer st = new StringTokenizer(bf.readLine());
            int a, b, c, result;
            a = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            c = Integer.parseInt(st.nextToken());
            if(a == -1 && b == -1 && c == -1) break; //종료조건
            result = w(a, b, c);
            StringBuilder printSet = new StringBuilder();
            printSet.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(result).append("\n");
            System.out.print(printSet);
        }
    }
    static int w(int a, int b, int c) {
        if(a <= 0 || b <= 0 || c <= 0) {
            wSet[0][0][0] = 1;
            return 1;
        }
        if(a > 20 || b > 20 || c > 20) {//바로 위 if문과 이 부분 때문에 wSet 배열의 크기가 저렇게 정해짐
            wSet[20][20][20] = w(20, 20, 20);
            return wSet[20][20][20];
        }

        if(wSet[a][b][c] != 0) //이미 계산되어 있는 경우
            return wSet[a][b][c];
        
        if(a < b && b < c) {
            wSet[a][b][c] = (w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c));
            return wSet[a][b][c];
        }
        
        wSet[a][b][c] = (w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1));
        return wSet[a][b][c];
    }
}