백준 13398번 연속합 2

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        int d[] = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = a[i];
            if(i > 0) {
                d[i] = Math.max(d[i], d[i - 1] + a[i]);
            }
        }
        
        int d2[] = new int[n];
        for(int i = n - 1; i >= 0; i--) {
            d2[i] = a[i];
            if(i < n - 1) {
                d2[i] = Math.max(d2[i], d2[i + 1] + a[i]);
            }
        }
        
        int answer = d[0];
        for(int i = 0; i < n; i++) { // 수를 제거하지 않는 경우 
            answer = Math.max(answer, d[i]);
        }
        for(int i = 1; i < n - 1; i++) {
            answer = Math.max(answer, d[i - 1] + d2[i + 1]);
        }
        System.out.println(answer);
    }
}

D[i] = i번째에서 끝나는 최대 연속합
D2[i] = i번째에서 시작하는 최대 연속합
이 값을 이용해서 A[i]를 제거했을 때 최대 연속합을 구할 수 있다.
i번째 수를 제거하면 i-1번째 수와 i+1번째 수가 연속하게 된다.

=> D[i-1] + D2[i+1]이 i번째 수를 제거했을 때 i번째 수가 포함되는 최대 연속합

결과

백준 2133번 타일 채우기

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long d[] = new long[n + 1];
        
        d[0] = 1;
        for(int i = 2; i <= n; i+= 2) {
            d[i] = d[i - 2] * 3;
            for(int j = i - 4; j >= 0; j -= 2) {
                d[i] += d[j] * 2;
            }
        }
        System.out.println(d[n]);
    }
}

D[i] = 3 x i를 채우는 방법의 수
D[i] = D[i - 2] 3 이 아니라, 가능한 경우가 더 있다.
D[i] = 3 D[i - 2] + 2 D[i - 4] + 2 D[i - 6] + ...

결과

백준 17404번 RGB 거리 2

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int a[][] = new int[n + 1][3];
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 3; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        int d[][] = new int[n + 1][3];
        int answer = 1000 * 1000 + 1;
        for(int k = 0; k <= 2; k++) {
            for(int j = 0; j <= 2; j++) {
                if(j == k) {
                    d[1][j] = a[1][j];
                } else {
                    d[1][j] = 1000 * 1000 + 1;
                }
            }
            for(int i = 2; i <= n; i++) {
                d[i][0] = Math.min(d[i - 1][1], d[i - 1][2]) + a[i][0];
                d[i][1] = Math.min(d[i - 1][0], d[i - 1][2]) + a[i][1];
                d[i][2] = Math.min(d[i - 1][0], d[i - 1][1]) + a[i][2];
            }
            for(int j = 0; j <= 2; j++) {
                if(j == k) continue;
                answer = Math.min(answer, d[n][j]);
            }
        }
        System.out.println(answer);
    }
}

1번 집의 색상을 미리 정해놓은 다음, 다이나믹을 3번 수행해서 정답을 구할 수 있다.

결과