[백준] 6193 Hungry Cows - Dynamic Programming / Java

graycode 2024. 1. 22. 17:21

• 문제 링크

6193번: Hungry Cows

Each of Farmer John's N (1 <= N <= 5,000) cows has a unique positive integer brand that fits nicely into 32 signed bits. He wishes the cows would line up in numerical order for feeding, but they never cooperate. To encourage good behavior, he allows a cow

www.acmicpc.net

• 풀이 코드

import java.io.BufferedWriter;
import java.io.IOException;
import java.io.OutputStreamWriter;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = read();
        int[] arr = new int[n], cache = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = read();
            cache[i] = 1;
        }

        int max = 0;
        for (int i = 0; i < n; max = Math.max(max, cache[i++]))
            for (int j = 0; j < i; j++)
                if (arr[i] > arr[j] && cache[i] <= cache[j]) cache[i] = cache[j] + 1;

        bw.write(String.valueOf(max));
        bw.flush();
    }

    private static int read() throws IOException {
        int c, n = System.in.read() & 15;
        while ((c = System.in.read()) > 32) n = (n << 3) + (n << 1) + (c & 15);

        return n;
    }

}