자바 계단 오르기

문제

나의 풀이

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

D[i] = i번째 계단에 도착할 수 있는 방법의 수
한칸 또는 두칸을 오를 수 있기 때문에
D[i]에 오려면 D[i - 1]에서 오거나 D[i - 2]에서 오는 경우 뿐이다. 따라서 이 둘의 경우의 수를 합하면 D[i]의 값이 구해진다.
따라서, 점화식을 정리해보면
D[i] = D[i - 1] + D[i - 2] 이다.

결과

자바 돌다리 건너기

문제

나의 풀이

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

앞선 문제와 똑같으나, 돌다리를 건너야 하기 때문에 마지막 돌까지 오는 경우의 수인 d[n]이 아니라 모두 건너선 맞은편 땅에 도달하는 방법의 수인 d[n + 1]을 구하는 걸로 하면 된다.

결과

자바 최대부분증가수열(LIS)

문제

나의 풀이

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

결과

자바 가장 높은 탑 쌓기(LIS 응용)

문제

나의 풀이

import java.util.*;

public class Main {
    static class Brick implements Comparable<Brick> {
        public int s, h, w;
        Brick(int s, int h, int w) {
            this.s = s;
            this.h = h;
            this.w = w;
        }
        @Override
        public int compareTo(Brick o) {
            return o.s - this.s; // 넓이에 대해 내림차순 정렬
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Brick> arr = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            arr.add(new Brick(a, b, c));
        }

        Collections.sort(arr);

        int d[] = new int[n];
        d[0] = arr.get(0).h;
        int answer = d[0];
        for(int i = 1; i < n; i++) {
            int max = 0;
            for(int j = i - 1; j >= 0; j--) {
                if(arr.get(j).w > arr.get(i).w && d[j] > max) {
                    max = d[j];
                }
            }
            d[i] = max + arr.get(i).h;
            answer = Math.max(answer, d[i]);
        }
        System.out.println(answer);
    }
}

넓이에 대해 내림차순 정렬을 한다.
d[i] = i번째 벽돌이 가장 최정상에 있을 때 탑의 최대 높이

결과