백준 15988번 1,2,3 더하기 3

문제

나의 풀이

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        long d[] = new long[1000001];
        d[0] = 1;

        for(int i = 1; i <= 1000000; i++) {
            for(int j = 1; j <= 3; j++) {
                if(i - j >= 0) {
                    d[i] += d[i - j];
                }
            }
            d[i] %= 1000000009L;
        }

        int t = sc.nextInt();
        for(int i = 0; i < t; i++) {
            int n = sc.nextInt();
            System.out.println(d[n]);
        }
    }
}

기존 1,2,3 더하기 문제에서 100000009으로 나누어주는 연산을 추가해준다.

결과

백준 1149번 RGB거리

문제

나의 풀이

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];
        int d[][] = new int[n + 1][3];
        for(int i = 1; i <= n; i++) {
            for(int j = 0; j < 3; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        
        for(int i = 1; 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];
        }
        System.out.println(Math.min(Math.min(d[n][0], d[n][1]), d[n][2]));
    }
}

D[i][j] = i번 집을 색 j로 칠했을 때, 1~i번 집을 칠하는 비용의 최소값으로 한다. (j=0->빨강, j=1->초록, j=2->파랑)
A[i][j] = i번집을 색j로 칠하는 비용의 최소값이다.

1. D[i][0] = min(D[i-1][1], D[i-1][2]) + A[i][0]
2. D[i][1] = min(D[i-1][0], D[i-1][2]) + A[i][1]
3. D[i][2] = min(D[i-1][0], D[i-1][1]) + A[i][2]
   라고 할 수 있다.

따라서 D[i][j]는 1,2,3 중 최솟값이라고 할 수 있다.

결과

백준 1309번 동물원

문제

나의 풀이

import java.util.*;

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

D[N][0] = N번 줄에 배치하지 않음
D[N][1] = N번 줄의 왼쪽에만 배치함
D[N][2] = N번 줄의 오른쪽에만 배치함

이런 경우 점화식은 이렇게 세울 수 있다.

1. D[N][0] = D[N-1][0] + D[N-1][1] + D[N-1][2]
2. D[N][1] = D[N-1][0] + D[N-1][2]
3. D[N][2] = D[N-1][0] + D[N-1][1]

경우의 수를 구하는 문제이므로 이들의 결과값을 모두 더해주면 된다.

결과