[백준] 14. 동적계획법1 - Java코드😨

https://www.acmicpc.net/step/16

동적 계획법 1 단계

동적계획법은 메모이제이션이 핵심!

단순하게 연산이 반복되는 문제나, 여러 재귀호출이 있는 경우, 또는 이전연산으로 이후의 결과를 만들수있는 경우에

DP 개념을 도입해 값을 캐싱하도록 구현하므로 보다 빠르게 문제를 해결하는 방법이다.   

 

목차

✅ 1 1003  피보나치 함수  31.311%
✅ 2 9184  신나는 함수 실행 41.947%
✅ 3 1904  01타일 32.360%
✅ 4 9461  파도반 수열 41.897%
✅ 5 1149  RGB거리 50.640%
✅ 6 1932  정수 삼각형 58.635%
✅ 7 2579  계단 오르기 34.247%
✅ 8 1463  1로 만들기 32.128%
✅ 9 10844  쉬운 계단 수 29.347%
✅ 10 2156  포도주 시식 32.755%
✅ 11 11053  가장 긴 증가하는 부분 수열 37.257%
✅ 12 11054  가장 긴 바이토닉 부분 수열 50.781%
✅ 13 2565  전깃줄 46.921%
✅ 14 9251  LCS 40.434%
✅ 15 1912  연속합 33.236%
✅ 16 12865  평범한 배낭 35.309%

이번 단계에서는 생각보다 난이도 있는 문제가 많이있었으며,

피보나치의 개념이 들어간 문제도 꽤 많이 나왔다.

시간이 날때마다 풀어서 추가적으로 올릴 예정입니다

 

✅ 1 1003  피보나치 함수  31.311%

import java.util.Scanner;

public class 피보나치함수 {
    static StringBuilder sb = new StringBuilder();
    static Integer[][] arr = new Integer[41][2];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        arr[0][0] = 1;
        arr[0][1] = 0;
        arr[1][0] = 0;
        arr[1][1] = 1;
        for(int i=0;i<T;i++){
            int n = sc.nextInt();
            Integer[] tmp = fibo(n);
            sb.append(tmp[0]).append(" ").append(tmp[1]).append("\n");
        }
        System.out.println(sb);
    }
    static Integer[] fibo(int n){
        if(arr[n][0] == null) {
            arr[n][0] = fibo(n - 2)[0] + fibo(n - 1)[0];
            arr[n][1] = fibo(n - 2)[1] + fibo(n - 1)[1];
        }
        return arr[n];
    }
}

 

✅ 2 9184  신나는 함수 실행 41.947%

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 23,820 kb , 296 ms
// 메모이제이션을 Array[21][21][21]로 구현하여 사용
public class Main {
    static int[][][] arr = new int[21][21][21];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder(); // 결과 반환
        while(true){
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            if(a ==-1 && b ==-1 && c == -1)
                break;
            int res = w(a,b,c);
            sb.append("w(").append(a).append(", ").append(b).append(", ").append(c).append(") = ").append(res).append("\n");
        }
        System.out.println(sb);
    }
    public static int w(int a, int b, int c){
        // 하나라도 0이하는 바로 1 반환
        if(a <= 0 || b <= 0 ||c <= 0) {
            return 1;
        }
        // 하나라도 20 초과시 w(20,20,20) =  1048576 반환
        if(a > 20 || b > 20 || c > 20) {
            return 1048576;
        }
        // 메모이제이션 활용 - 이미 했던 연산값은 바로 가져옴
        if(arr[a][b][c] != 0)
            return arr[a][b][c];
        // 그 외 case는 아래와 같이 호출과정을 거침
        if(a<b && b<c) {
            return arr[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);
        }
        return  arr[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);
    }
}

 

 

✅ 3 1904  01타일 32.360%

import java.util.Scanner;

public class 타일 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[1000001]; // 왜 n+1이 안되는거지? 반복사용할것도 아니면서..
        arr[0] = 0;
        arr[1] = 1;
        arr[2] = 2;
        for (int i = 3; i <= n; i++)
            arr[i] = (arr[i-2] + arr[i-1]) %15746;
        System.out.println(arr[n] %15746);
    }
}

%15746 은 미리미리 저장할때부터 해주자. 

그래야 overflow를 막을수 있다.

 

✅ 4 9461  파도반 수열 41.89%

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
// 주의 ! - 피보나치는 기하급수적으로 수가 커지므로 overflow를 주의하여 Long을 쓰자
public class 파도반수열 {
    static Long[] arr = new Long[101];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int T = Integer.parseInt(br.readLine());
        arr[0] = 0L;
        arr[1] = 1L;
        arr[2] = 1L;
        arr[3] = 1L;
        int n;
        for (int i = 0; i < T; i++) {
             n  = Integer.parseInt(br.readLine());
            sb.append(fibo(n)).append("\n");
        };
        System.out.println(sb);
    }
    static Long fibo(int n){
        if(arr[n] == null)
            arr[n] = fibo(n-3) + fibo(n-2);
        return arr[n];
    }
}

피보나치는 기하급수적으로 수가 커지므로 overflow를 주의하여 Long을 쓰자

 

✅ 5 1149  RGB거리 50.640%

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

public class RGB거리 {
    static int[][] cost;
    static int[][] DP;
    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        cost = new int[n][3];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j = 0; j < 3; j++) {
                cost[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
        // DP - 3가지 경우로 메모이제이션!
        // 마지막이 red, green, blue 를 각각 선택한 경우들을
        // 뒤에서 역으로 최소선택을 추적해가도록 백트래킹

        DP = new int[n][3];
        DP[0][0] = cost[0][0];
        DP[0][1] = cost[0][1];
        DP[0][2] = cost[0][2];
        int res = Math.min(record_cost(n-1,0), Math.min(record_cost(n-1,1), record_cost(n-1,2)));
        System.out.println(res);
    }
       static int record_cost(int i, int j){
        int a = (j+1) % 3;
        int b = (j+2) % 3;
        if(DP[i][j]==0)
            DP[i][j] = cost[i][j] + Math.min(record_cost(i-1,a), record_cost(i-1,b));
        return DP[i][j];
    }
}

1. 마지막이 red, green, blue를 선택했을때의 각각의 3가지의 경우의 값을 모두 구해서 최솟값을 비교한다. 

2. record_cost라는 DP함수를 백트래킹으로 구현했다.

3. 그 안에서 탐색 하고자 하는 color값이 아닌 두개의 비교 인덱스 a, b는 위와같이 3으로 나누어 구해주었다. 

✅ 6 1932  정수 삼각형 58.635%

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

public class 정수삼각형 {
    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] arr = new int[n][n];
        StringTokenizer st;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine()," ");
            int j=0;
            while(st.hasMoreTokens()){
                arr[i][j++] = Integer.parseInt(st.nextToken());
            }
        }
        br.close();
		// botton up
        for (int i = n-2; i >= 0; i--) {
            for (int j = 0; j <= i; j++)
                arr[i][j] += Math.max(arr[i+1][j],arr[i+1][j+1]);
        }
        System.out.println(arr[0][0]);
    }
}

탑 다운 방식으로 구현하면, 모든 경우를  계속해서 비교하며 변경해주게 된다.

이런 트리형태의 자료가 주어지면, 역으로 뒤집어 올라가도록 생각해야한다.

 

 

✅ 7 2579  계단 오르기 34.247%

문제 핵심

1. 계단을 오를 때 한번에 1-2 계단을 오를 수 있다.

2. 계단을 하나씩 3개 이상 밟으면 안된다.

3. 마지막 계단은 '반드시' 밟아야 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 계단오르기 {
    //Integer 배열은 초기값이 null이므로 활용
    static int[] cost;
    static Integer[] DP;
    public static void main(String[] args) throws IOException {
        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        cost = new int[n+1];
        // 1번 부터 셋팅 (0번째는 null이 아닌 0을 가져야함)
        for (int i = 1; i <= n; i++)
            cost[i] = Integer.parseInt(br.readLine());
        br.close();
        // DP
        DP = new Integer[n+1];
        DP[0] = cost[0];
        DP[1] = cost[1];
        if(n>=2) // 최대값으로 셋팅
            DP[2] = cost[1]+ cost[2];
        System.out.println(record_cost(n));
    }
    static int record_cost(int n){
        // (n-3 + n-1 + n)을 밟는 경우와 (n-2 + n)을 경우를 비교 = 연속 두번까지만 밟게 방어
        if(DP[n]==null)
            DP[n] = cost[n] + Math.max(record_cost(n-2), record_cost(n-3) + cost[n-1]);
        return DP[n];
    }
}

TopDown방식으로 바라볼때, 맨끝에서 두번까지만 밟는 경우들을 탐색하여 최솟값을 비교해주었다.

핵심로직이 뒤에 세번째까지는 값이 있어야하므로 0,1,2는 초기화가 필요하다.

1이상인 경우만 들어오므로 2는 2이상인 경우만 초기화해준다.

 

✅ 8 1463  1로 만들기 32.128%

import java.util.Scanner;

public class 일로만들기 {
    static int[] arr;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n+1];
        sc.close();
        arr[1] = 0;
        // DP
        Func(n);
        System.out.println(arr[n]);

    }
    static int Func(int n){
        if(n==1 || arr[n]!=0)
            return arr[n];
        int a=Integer.MAX_VALUE,b=Integer.MAX_VALUE,c;
        if(n%3==0)
            a = Func(n/3)+1;
        if(n%2==0)
            b = Func(n/2)+1;
        c= Func(n-1)+1;
        return arr[n] += Math.min(c,Math.min(a,b));
    }
}

 

✅ 9 10844  쉬운 계단 수 29.347%

import java.util.Scanner;

public class 쉬운계단수 {
    static int n;
    static Long[][] arr;
    final static long MOD = 1000000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new Long[n+1][10];
        sc.close();
        long result =0L;
        for (int i = 0; i < 10; i++) {
             arr[1][i] = 1L;
        }
        for (int i = 1; i < 10; i++) { // 첫자리는 0이 올 수 없다
             result += func(n,i);
        }
        System.out.println(result % MOD);
    }
    static Long func(int digit,int val){ // 몇번째 자리인지, 해당자리의 값
        if(digit==1) // 원하는 길이만큼 만들어졌으면 반환
            return arr[1][val];
        if(arr[digit][val] == null){ // 아직 안구해졌으면 구해주고 반환
            if(val==0)
                arr[digit][val] = func(digit-1,1); // 0이면, 올라가는 경우만 존재
            else if(val==9)
                arr[digit][val] = func(digit-1,8); // 9이면, 내려가는 경우만 존재
            else
                arr[digit][val] = func(digit-1,val+1) + func(digit-1,val-1);
        }
        return arr[digit][val] % MOD;
    }
}

 

 

✅ 10 2156  포도주 시식 32.755%

보통 2번 연속을 막기위해서 f(n-2) + arr[n] 과 f(n-3) + arr[n-1] 을 비교할뿐 아니라,

f(n-1)번째까지 총 3개의 case를 비교해주어야 한다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class 포도주시식 {
    static int[] arr;
    static Integer[] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        arr = new int[n+1];
        dp = new Integer[n+1];
        for (int i = 1; i <= n; i++) arr[i] = Integer.parseInt(br.readLine());
        dp[0] = 0;
        dp[1] = arr[1];
        if(n>=2)
            dp[2] = arr[1] + arr[2];

        System.out.println(func(n));
        br.close();
    }
    /*
    3가지 경우를 비교한다.
    1. f(n-3) + a[n-1] + a[n] -> 2번 연속되더라도 n-3번째까지의 합에서 연속되도록
    2. f(n-2) + a[n]        ->  2번이 연속되지 않도록
    3. f(n-1)               -> 마지막 값을 안뽑는 경우가 더 클수가 있으므로 비교가 필요하다 (생각하기 어렵다)
     */
    static int func(int n){
        if(dp[n] == null)
            return dp[n] = Math.max(Math.max(func(n-3) + arr[n-1]+ arr[n], func(n-2) + arr[n]),func(n-1));
        return dp[n];
    }
}

 

✅ 11 11053  가장 긴 증가하는 부분 수열 37.257%

✅ 12 11054  가장 긴 바이토닉 부분 수열 50.781%

✅ 13 2565  전깃줄 46.921%

✅ 14 9251  LCS 40.434%

✅ 15 1912  연속합 33.236%

✅ 16 12865  평범한 배낭 35.309%

 

문제가 많아서 오래 걸리고 뒤 문제들은 난이도가 상당하네요ㅠ