[Algorithm] 백준 단계별로 풀어보기 - 단계 12. 동적 계획법1-(1)

동적 계획법 기초, 응용

2748. 피보나치 수 2

시간 제한이 있으므로 동적계획법(DP) 활용해야한다. Top-Down 방식을 활용해서 풀었음.

배열을 미리 -1로 다 채워놓고, fibo 메서드를 실행시킨 다음 해당 배열에 값을 채운다.

이미 실행되어 배열에 값이 존재할 경우 그 값을 그대로 사용한다. => 메모이제이션

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(rd.readLine());
        rd.close();

        //메모이제이션
        long[] fiboArr = new long[n+1];
        Arrays.fill(fiboArr, -1);

        long result = fibo(n, fiboArr);
        System.out.println(result);
    }

    static long fibo(int n, long fiboArr[]) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        if(fiboArr[n] != -1) {
            //배열에 저장된 값이 있을 경우
            return fiboArr[n];
        }
        //배열에 저장된 값이 없을 경우
        fiboArr[n] = fibo(n-1, fiboArr) + fibo(n-2, fiboArr);
        return fiboArr[n];
    }
}

1003. 피보나치 함수

피보나치 수열을 실행시켰을 때 0이 출력되는 횟수와 1이 출력되는 횟수를 출력한다.

0이 출력되는 횟수는 fibo(n-1), 1이 출력되는 횟수는 fibo(n)이라는 규칙을 적용하여 푼 문제.

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(rd.readLine());

        long[] fiboArr = new long[41];
        Arrays.fill(fiboArr, -1);

        int n;
        for(int i=0; i<T; i++) {
            n = Integer.parseInt(rd.readLine());
            if(n == 0) System.out.println("1 0");
            else System.out.println(fibo(n-1, fiboArr)+" "+fibo(n, fiboArr));
        }
    }

    static long fibo(int n, long fiboArr[]) {
        if(n == 0) return 0;
        if(n == 1 || n == 2) return 1;

        if(fiboArr[n] != -1) {
            return fiboArr[n];
        }
        fiboArr[n] = fibo(n-1, fiboArr) + fibo(n-2, fiboArr);
        return fiboArr[n];
    }
}

1904. 01타일

피보나치 수열을 이용하면 풀 수 있는 응용문제

% 15726을 하지 않고 배열에 넣게되면 수가 어마어마해지므로 주의!

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(rd.readLine());

        int dp[] = new int[1000000];
        dp[0] = 0; dp[1] = 1; dp[2] = 2;

        for(int i=3; i<=N; i++) {
            dp[i] = (dp[i-1] + dp[i-2]) % 15746;
        }
        System.out.println(dp[N]);
    }
}

9461. 파도반 수열

P(1)~P(5)까지는 규칙을 찾을 수 없으므로 각각 초기화해준다.

P(6)부터는 (i-1) + (i-5)해주며 Bottom-up 방식으로 배열을 채워 문제를 해결하였다.

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

public class BOJ_9461 {
    public static void main(String[] args) throws Exception {
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(rd.readLine());

        long arr[] = new long[101];
        arr[0] = 0;
        arr[1] = arr[2] = arr[3] = 1;
        arr[4] = arr[5] = 2;
        for(int i=6; i<=100; i++) {
            arr[i] = arr[i-1] + arr[i-5];
        }

        for(int i=0; i<T; i++) {
            int N = Integer.parseInt(rd.readLine());
            System.out.println(arr[N]);
        }
    }
}

1149. RGB 거리

i번째 집을 각각의 색으로 칠할 때, 1~i번째 집을 모두 칠하는 최소 비용으로 부분문제를 정의하는 문제

	R	G	B
A	26	40	83
B	49	60	57
C	13	89	99
D	40	90	10

2차원 배열에 위와 같이 입력되었다. 서로 이웃하고 있으면 연달아 같은 색을 칠할 수 없다는 조건이 주어진다.

A, B는 같은 색을 칠할 수 없지만 A, C는 같은 색을 칠할 수 있다.

 

최소 비용을 구해야하므로, A가 R G B 중 최소값인 26을 선택하였을 때, B는 R을 제외한 G B를 선택할 수 있다.

B가 G B 중 최소값인 57(B)을 선택하였을 때, C는 R G를 선택할 수 있다.

C가 R G 중 최소값인 13(R)을 선택하였을 때, D는 G B를 선택할 수 있다.

index의 마지막인 D가 G B중 최소값인 10을 선택하면 A가 RED로 시작하였을 때 A, B, C, D를 칠하는 최소값을 구할 수 있다.

 

하지만, 첫번째 A를 RED로 칠하는 것이 최소값이라고 단정지어 생각할 수는 없다.

그 다음에 B C D에 올 수가 최소값이 아닐 수도 있기 때문이다.

위와 같은 경우, A를 B로 칠하는 경우인 106이 최소값이다.

 

그렇기 때문에 R, G, B를 모두 선택할 경우를 따져 문제를 풀어주어야 한다.

더한 수를 계속해서 누적시키면, D에는 최종적으로 칠할 수 있는 경우 3가지가 저장되어 있는데, 이 중 최소값을 출력시켜주면 되는 문제이다.

 

처음에 문제가 한번에 이해가 되지 않아서 헤맸지만, DP를 응용할 수 있는 간단한 문제였다.

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

public class BOJ_1149 {
    static int R = 0;
    static int G = 1;
    static int B = 2;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int color[][] = new int[N][3];

        for(int i=0; i<N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            color[i][R] = Integer.parseInt(st.nextToken());
            color[i][G] = Integer.parseInt(st.nextToken());
            color[i][B] = Integer.parseInt(st.nextToken());
        }

        for(int i=1; i<N; i++) {
            color[i][R] = color[i][R] + Math.min(color[i-1][G], color[i-1][B]); //red 선택
            color[i][G] = color[i][G] + Math.min(color[i-1][R], color[i-1][B]); //green 선택
            color[i][B] = color[i][B] + Math.min(color[i-1][R], color[i-1][G]); //blue 선택
        }

        System.out.print(Math.min(color[N-1][R], Math.min(color[N-1][B], color[N-1][G])));
    }
}

1932. 정수 삼각형

각 층의 모든 칸마다 최댓값을 저장하면서 동적 계획법으로 푸는 문제

위 문제와 같이 계속해서 더해 나가며 최대값을 찾아야 한다. 왼쪽, 오른쪽 대각선으로 더할 수 있기 때문에 이를 고려해야함.

배열 크기를 +1 하여 선언한 후 index를 1부터 시작하며 풀었다.

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

public class BOJ_1932 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int tri[][] = new int[N+1][N+1];

        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=1; j<=i; j++) {
                tri[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        int max = 0;
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=i; j++) {
                if(j == 0) { //왼쪽 테두리
                    tri[i][j] = tri[i][j] + tri[i-1][j];
                } else if(j == i) {//오른쪽 테두리
                    tri[i][j] = tri[i][j] + tri[i-1][j-1];
                } else {
                    tri[i][j] = Math.max(tri[i-1][j-1], tri[i-1][j]) + tri[i][j];
                }
                //최대값 저장
                if (max < tri[i][j])
                    max = tri[i][j];
            }
        }
        System.out.print(max);
        br.close();
    }
}

2597. 계단 오르기

조건 1. 계단은 한번에 한 계단, 두 계단씩

조건 2. 연속된 세 개의 계단 X (시작점은 포함되지 않는다)

조건 3. 마지막 계단은 반드시 밟기

합한 값을 저장할 result 배열을 따로 만들어주었다.

 

dp 배열의 모든 index에 접근하여 전 칸을 밟았을 경우(한 칸 이동), 전 칸을 밟지 않았을 경우(두 칸 이동)를 계산했다.

 

첫 번째 칸은 그대로 dp[1] 값을 넣어주면 되고, dp[2]의 값은 dp[1] + dp[2]의 값으로 초기화하고 시작한다.

바로 전 칸을 밟았을 때, dp[i-1] + dp[i] + result[i-3]

두 칸 전을 밟았을 때, dp[i] + result[i-2] 로 계산해서 더 큰 값을 result에 넣어준다.

 

index 4로 예를 들어본다면, index 4로 올 수 있는 경우는 index 2와 index 3일 때이다.

바로 전 칸을 밟았을 때는 15 + 25 + 10 = 55 이다.

전 칸을 밟지 않았을 때는 25 + 30  = 55 이다. 따라서 55가 result 4에 들어간다.

 

index 3, 5는 밟지 않은 index인데, 이러한 경우 반복문에 따라 값은 계산되지만 최종적인 값 출력에는 포함되지 않는다.

(단계마다 최대값을 result에 누적하고, 최종적으로 마지막 배열이 전 칸을 밟았는지, 밟지 않았는 지에 따라 최대값이 출력되기 때문)

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

public class BOJ_2579 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N+1];
        int result[] = new int[N+1];

        for(int i=1; i<=N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            dp[i] = Integer.parseInt(st.nextToken());
        }

        result[1] = dp[1];
        result[2] = dp[1] + dp[2];
        for(int i=3; i<=N; i++) {
            result[i] = Math.max(dp[i-1] + dp[i] + result[i-3], dp[i] + result[i-2]); //한 칸, 두 칸
        }

        System.out.print(result[N]);
    }
}

1463. 1로 만들기

메모이제이션으로 N을 1로 바꾸기 위해 주어진 연산을 몇 번 사용하는지 계산하는 문제

 

점화식 찾는게 쉽지 않은 것 같다. 다른 분의 풀이를 보고 이해한 문제..

Top-Down 보다는 Bottom-up 방식이 이해하기가 더 쉬워서 Bottom-up으로 풀었다.

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

public class BOJ_1463 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int dp[] = new int[1000000+1];
        dp[0] = dp[1] = 0;

        for(int i=2; i<=N; i++) {
            dp[i] = dp[i-1] + 1;
            if(i%2 == 0) dp[i] = Math.min(dp[i/2] + 1, dp[i]);
            if(i%3 == 0) dp[i] = Math.min(dp[i/3] + 1, dp[i]);
        }

        System.out.println(dp[N]);
    }
}

일단 이 문제는, -1로 빼는 경우, 2로 나누는 경우, 3으로 나눈 경우 중 가장 최소가 되는 값을 저장시켜 주며 문제를 풀어여 한다.

0과 1일 때는 0이므로 미리 초기화해주고 10이 주어졌을 때, 2부터 1로 만드는 최소값을 저장한다.

1을 뺐을 때를 고려해서 dp[2] 에 dp[1] + 1 을 넣어준다.

1을 더해주는 이유는 -1로 연산을 수행했으므로 연산 횟수 증가를 위해서이다.

 

하지만 1을 뺐을 때가 최소가 아닐 수 있다. 그러므로 나누기 2, 나누기 3을 모두 고려해줘야한다.

2는 2로 나누어 떨어지지만 3으로 나누어 떨어지지 않으므로, dp[2/2] + 1 해주고, 만약 -1해준 것보다 값이 작다면 dp[i]에 나누기 2해준 값을 넣어준다.

dp[1]에는 이미 연산된 0이라는 수가 들어있는데(작은 문제부터 해결), 이에 연산 횟수 1을 더하여 dp[2]에 넣어주는 것이다.

 

이러한 식으로 계속해서 작은 값부터 채워 나아가며 최소값을 구한다.

10844. 쉬운 계단 수

출력 형식에 주의! 1000000000으로 나눈 나머지를 출력해 주어야 한다.

 

한 자리일 경우 앞자리에 0이 올 수 없다는 조건이 붙었으므로 1로 배열을 초기화해준다.

dp[자리수][끝자리]에서 끝자리가 0 혹은 9일 경우 +1, -1해주었을때 index를 넘어가게 되므로 이 경우 if문을 따로 걸어주었다.

2부터 자리수 N까지(i), 0부터 9까지(j) 반복하며 2차원 배열을 채워주면 된다.

 

dp[3][2]를 예로 들자면, 자리수는 3자리이고 2로 끝나는 수를 찾으려고 한다. 212, 232, 432 총 3개가 가능함.

이 경우 아래 점화식에 따르면 dp[3][2] = dp[2][1] + dp[2][3]이다. 그리고 이를 다시 바꿔보면 아래와 같다.

dp[2][1] = dp[1][0] + dp[1][2]

dp[2][3] = dp[1][2] + dp[1][4]

 

2차원 배열 dp에는 계단 수가 총 몇개 있는지가 들어있다.

dp[1][0] = 0, dp[1][2] = 1, dp[1][2] = 1, dp[1][2] = 1

따라서, dp[2][1] = 1, dp[2][3] = 2가 되고, dp[3][2]에는 3이 들어가게 된다.

 

이와 같은 식으로 1단계부터 계단 수를 채워 나아가며 최종적으로 입력받은 N의 계단 수를 출력하는 문제이다.

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

public class BOJ_10844 {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] dp = new int[N+1][11];

        //한 자리일 경우 미리 초기화 - 앞자리 0이 올 수 없기 때문
        dp[1][0] = 0;
        for(int i=1; i<=9; i++) {
            dp[1][i] = 1;
        }
        for(int i=2; i<=N; i++) {
            for(int j=0; j<=9; j++) {
                if(j == 0) {
                    dp[i][j] = dp[i-1][j+1] % 1000000000;
                } else if(j == 9) {
                    dp[i][j] = dp[i-1][j-1] % 1000000000;
                } else {
                    dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % 1000000000;
                }
            }
        }

        long sum = 0;
        for(int i=0; i<=9; i++) {
            sum += dp[N][i];
        }
        System.out.print(sum % 1000000000);
    }
}