[백준] 11055 : 가장 큰 증가하는 부분수열

가장 긴 증가하는 부분수열에서 살짝 변형된 문제였다.

DP초기화를 같은 인덱스 위치의 수를 그대로 넣어서 해주는 것만 달랐음.

 

1등 코드

메모리 : 13260 KB

시간 : 88 ms

코드길이 : 1033 B

 

내 코드

메모리 : 14944 KB

시간 : 152 ms

코드길이 : 885

 

[1등 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static int N;
	static int max;
	static int[] arr = new int[1001];
	static int[] D = new int[1001];//D[i] = 현재까지 i로 끝나는 증가 부분 수열의 합 중 최대값
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i<=N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		int num;
		for(int i = 1; i<=N; i++) {
			num = maxSeries(arr[i]);
			if(num>D[arr[i]]) {
				D[arr[i]] = num;
				if(max<num) {
					max = num;
				}
			}
		}
		System.out.println(max);
	}
	static int maxSeries(int num) {
		int temp = 0;
		for(int i = 1; i<num; i++) {
			if(D[i]>temp)
				temp = D[i];
		}
		return temp+num;
	}
}

[내 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder sb = new StringBuilder();
		
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] DP = new int[N];
		
		st = new StringTokenizer(br.readLine());
		for(int n = 0; n < N; n++) {
			arr[n] = Integer.parseInt(st.nextToken());
			DP[n] = arr[n];
		}
		
		int result = DP[0];
		
		for(int i = 1; i < N; i++) {
			int plus = 0;
			for(int j = 0; j < i; j++) {
				if(arr[i] > arr[j] && DP[j] > plus)
					plus = DP[j];
			}
			DP[i] += plus;
			if(DP[i] > result)
				result = DP[i];
		}
		
		sb.append(result);
		System.out.print(sb);
		
	}

}