백준 10844번 쉬운 계단 수

문제

나의 풀이

import java.util.Scanner;

public class Main {
    static final long mod = 1000000000;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long d[][] = new long[n + 1][10];
        for(int i = 1; i <= 9; i++) {
            d[1][i] = 1;
        }
        for(int i = 2; i <= n; i++) {
            d[i][0] = d[i - 1][1]; // L+1만 해야됨
            d[i][9] = d[i - 1][8]; // L-1만 해야됨
            for(int j = 1; j <= 8; j++) {
                d[i][j] = (d[i - 1][j - 1] + d[i - 1][j + 1]) % mod;
            }
        }

        long sum = 0;
        for(int i = 0; i < 10; i++) {
            sum += d[n][i];
        }
        sum %= mod;
        System.out.println(sum);
    }
}

D[N][L] = 길이가 N인 계단 수. 마지막으로 사용한 수가 L
N-1번째에 올 수 있는 수는 L-1, L+1이다.
즉, 경우의 수는 D[N-1][L-1] + D[N-1][L+1]이다.
하지만 L=0인 경우 L-1을 할 수 없고, L=9인 경우 L+1을 할 수 없기 때문에 예외 처리를 해야 한다.

결과

백준 2193번 이친수

문제

나의 풀이

import java.util.Scanner;

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][2];
        d[1][1] = 1; 
        d[1][0] = 0;
        for(int i = 2; i <= n; i++) {
            d[i][0] = d[i - 1][1] + d[i - 1][0];
            d[i][1] = d[i - 1][0];
        }
        
        System.out.println(d[n][0] + d[n][1]);
    } 
}

D[N][L] = N자리 이친수. 마지막 수가 L.

1. D[N][0] : 마지막 수가 0인 경우에는 N-1번째 수가 0도 가능하므로
   D[N][0] = D[N-1][0] + D[N-1][1]
2. D[N][1] : 마지막 수가 1인 경우네느 N-1번째 수가 1은 불가능하므로
   D[N][1] = D[N-1][0]

초기값은 가장 짧은 이친수는 길이가 1이다.
D[1][0]은 이친수는 0으로 시작하지 않으므로 0이다.
D[1][1]은 1이다.

결과

백준 11053번 가장 긴 증가하는 부분 수열

문제

나의 풀이

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] = 1; 
            for(int j = 0; j < i; j++) {
                if(a[j] < a[i]) {
                    d[i] = Math.max(d[i], d[j] + 1);
                }
            }
        }
        
        int answer = d[0];
        for(int i = 0; i < n; i++) {
            if(answer < d[i]) {
                answer = d[i];
            }
        }
        System.out.println(answer);
    }
}

D[i] = A[1], ..., A[i]까지 수열이 있을 때 A[i]을 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
D[i] = max(D[j]) + 1 이다.
j의 범위는 i보다 작고, j번째 수가 i번째 수 보다 작아야 한다.

결과

백준 14002번 가장 긴 증가하는 부분 수열 4

문제

나의 풀이

import java.util.*;

public class Main {
    static int a[];
    static int d[];
    static int v[];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new int[n];
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        d = new int[n];
        v = new int[n];
        for(int i = 0; i < n; i++) {
            d[i] = 1;
            v[i] = -1;
            for(int j = 0; j < i; j++) {
                if(a[j] < a[i] && d[i] < d[j] + 1) {
                    d[i] = d[j] + 1;
                    v[i] = j;
                }
            }
        }

        int answer = d[0];
        int index = 0;
        for(int i = 0; i < n; i++) {
            if(answer < d[i]) {
                answer = d[i];
                index = i;
            }
        }
        System.out.println(answer);
        go(index);
        System.out.println();
    }

    static void go(int index) {
        if(index == -1) {
            return;
        }
        go(v[index]);
        System.out.print(a[index] + " ");
    }
}

D[i] = A[1], ..., A[i]까지 수열이 있을 때 A[i]을 마지막으로 하는 가장 긴 증가하는 부분 수열의 길이
V[i] = A[i]의 앞에 와야 하는 수의 인덱스. 즉, A[i]의 앞에는 A[V[i]]가 와야 길이가 가장 길다
정답을 출력할 때는 V[i]를 역추적하면 된다.

결과