Baekjoon - 11053

문제

Solved.ac Class4

1차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int size = Integer.parseInt(br.readLine());
		Set<Integer> set = new HashSet<>();

		String[] split = br.readLine().split(" ");
		for (int i = 0; i < size; i++) {
			set.add(Integer.parseInt(split[i]));
		}

		System.out.println(set.size());
	}
}

문제이해 미흡

실패

2차시도

public class Main {
	private static int[] data;
	private static int size;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;
		size = Integer.parseInt(br.readLine());
		data = new int[size];

		String[] split = br.readLine().split(" ");
		for (int i = 0; i < size; i++) {
			data[i] = Integer.parseInt(split[i]);
		}

		for (int i = 0; i < size; i++) {
			int solve = solve(i);
			answer = Math.max(answer, solve);
		}
		System.out.println(answer);

	}

	private static int solve(int visit) {
		int temp = 0;
		int now = 1;
		for (int i = visit + 1; i < size; i++) {
			if (data[visit] < data[i]) {
				int solve = solve(i);
				temp = Math.max(solve, temp);
			}
		}
		return temp + now;
	}
}

시간초과

3차시도

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int answer = 0;
		int size = Integer.parseInt(br.readLine());
		int[] data = new int[size];
		int[] dp = new int[size];

		String[] split = br.readLine().split(" ");
		for (int i = 0; i < size; i++) {
			data[i] = Integer.parseInt(split[i]);
		}

		for (int i = 0; i < size; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if (data[j] < data[i] && dp[i] <= dp[j]) {
					dp[i] = dp[j] + 1;
				}
			}
		}

		for (int i = 0; i < size; i++) {
			answer = Math.max(answer, dp[i]);
		}
		System.out.println(answer);
	}
}

DP를 적용하여 풀었다

성공