다이나믹 프로그래밍 1

1463번 1로 만들기

문제

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int dp[] = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + 1; // 1을 더한 것은 연산을 수행한 횟수 올려주는 것
            
            if(i % 3 == 0) {
                // 3 나누기 연산 수행한 것과 -1 연산 수행한 것 비교
                dp[i] = Math.min(dp[i], dp[i / 3] + 1);
            }
            if(i % 2 == 0) {
                // 2 나누기 연산 ㅜ행한 것과 -1 연산 수행한 것 비교
                dp[i] = Math.min(dp[i], dp[i / 2] + 1);
            }
        }
        System.out.println(dp[n]);
        
        sc.close();
    }
}

9095번 1, 2, 3 더하기

문제

풀이

import java.util.Scanner;

public class Main {
    static int cnt = 0;

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

        for(int i = 0; i < n; i++) {
            cnt = 0;
            int t = sc.nextInt();
            dfs(t, 0);
            System.out.println(cnt);
        }
    }

    public static void dfs(int t, int n) {
        if(t < n) {
            return;
        }
        if(t == n) {
            cnt++;
            return;
        } else {
            dfs(t, n + 1);		// 더하기 1
            dfs(t, n + 2);		// 더하기 2
            dfs(t, n + 3);		// 더하기 3
        }
    }
}

10844번 쉬운 계단 수

문제

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[][] dp = new long[n][10];

        for(int i = 1; i < 10; i++){
            dp[0][i] = 1;
        }

        for(int i = 1; i < n; i++){
            dp[i][0] = dp[i - 1][1]; // 0일때는 1 - 1일때만 가능
            dp[i][9] = dp[i - 1][8]; // 9일때는 8 + 1일때만 가능
            for(int j = 1; j < 9; j++){
                dp[i][j] = (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % 1000000000; // 나눈 나머지를 출력해야 하므로
            }
        }

        long sum = 0;
        for(int i = 0; i < 10; i++){
            sum += dp[n - 1][i];
        }
        System.out.println(sum % 1000000000);
        
        sc.close();
    }
}

1912번 연속합

문제

풀이

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int arr[] = new int[n];
        int dp[] = new int[n];
        
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = arr[0];
        int answer = dp[0];
        for(int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i - 1] + arr[i], arr[i]);
            if(dp[i] > answer) {
                answer = dp[i];
            }
        }
        System.out.println(answer);
    }
}

2225번 합분해

문제

풀이

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] dp = new int[k + 1][n + 1];
        
        for(int i = 0; i < n + 1; i++) {
            dp[1][i] = 1;
        }

        for(int i = 2; i < k + 1; i++) { 
            dp[i][0] = 1;
            for(int j = 1; j < n + 1; j++) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % 1000000000;
            }
        }
        System.out.println(dp[k][n]);
    }
}