์ ์ก๋ฉด์ฒด ๋ชจ์์ ์์๊ฐ ์ผ๋ ฌ๋ก ๋์ด์ ์๋ค. ์์๋ง๋ค ํฌ๊ธฐ๊ฐ ์ฃผ์ด์ ธ ์๋๋ฐ, ์์ ์๋ ์์์ ํฌ๊ธฐ๊ฐ ๋ค์ ์๋ ์์์ ํฌ๊ธฐ๋ณด๋ค ์์ผ๋ฉด, ์์ ์๋ ์์๋ฅผ ๋ค์ ์๋ ์์ ์์ ๋ฃ์ ์๊ฐ ์๋ค. ์๋ฅผ ๋ค์ด ์์์๋ถํฐ ์์๋๋ก ํฌ๊ธฐ๊ฐ (1, 5, 2, 3, 7)์ธ 5๊ฐ์ ์์๊ฐ ์๋ค๋ฉด, ํฌ๊ธฐ 1์ธ ์์๋ฅผ ํฌ๊ธฐ 5์ธ ์์์ ๋ฃ๊ณ , ๋ค์ ์ด ์์๋ฅผ ํฌ๊ธฐ 7์ธ ์์ ์์ ๋ฃ์ ์ ์๋ค. ํ์ง๋ง ์ด๋ ๊ฒ ์์๋ฅผ ๋ฃ์ ์ ์๋ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ ์ ์๋ค. ์์ ์์์ ์ฐจ๋ก๋๋ก ํฌ๊ธฐ๊ฐ 1, 2, 3, 7์ธ ์์๋ฅผ ์ ํํ๋ฉด ์ด 4๊ฐ์ ์์๊ฐ ํ ๊ฐ์ ์์์ ๋ค์ด๊ฐ๊ฒ ๋๋ค.
์์์ ํฌ๊ธฐ๊ฐ ์ฃผ์ด์ง ๋, ํ ๋ฒ์ ๋ฃ์ ์ ์๋ ์ต๋์ ์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ ํ๋ก๊ทธ๋จ์ ์์ฑํ์์ค.
์ ๋ ฅ
ํ์ผ์ ์ฒซ ๋ฒ์งธ ์ค์ ์์์ ๊ฐ์ n (1 โค n โค 1000)์ ๋ํ๋ธ๋ค. ๋ ๋ฒ์งธ ์ค์๋ ๊ฐ ์์์ ํฌ๊ธฐ๊ฐ ์์๋๋ก ์ฃผ์ด์ง๋ค. ์์์ ํฌ๊ธฐ๋ 1,000์ ๋์ง ์๋ ์์ฐ์์ด๋ค.
์ถ๋ ฅ
์ฒซ์งธ ์ค์ ํ ์ค์ ๋ฃ์ ์ ์๋ ์ต๋์ ์์ ๊ฐ์๋ฅผ ์ถ๋ ฅํ๋ค.
1) dp์ ์ด๊ธฐ๊ฐ์ 1
Arrays.fill(dp, 1);
2) arr ์์ ์ซ์๋ค๊ณผ ๋น๊ตํด์ ๋ ์์ index๋ค ์ค
dp๊ฐ ์ ์ผ ํฐ ๊ฐ+1์ ํ์ฌ dp ๊ฐ์ ์ ํจ
right[m] = dp[r-1][m] + map[r][m];
for(int c=m-1; c>=1; c--)
right[c] = Math.max(right[c+1], dp[r-1][c]) + map[r][c];
๋ ๊ฐ์ ๊ฒฐ๊ณผ๊ฐ ์ค ๋ ํฐ ๊ฐ dp์ ์ ์ฅ
for(int i=2; i<n; i++) {
for(int j=0; j<i; j++) {
if(arr[i] > arr[j])
dp[i] = Math.max(dp[i], dp[j]+1);
}
}
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
public class DP_10 {
static int arr[], n, dp[];
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
arr = new int[n];
dp = new int[n];
String s[] = br.readLine().split(" ");
for(int i=0; i<n; i++)
arr[i] = Integer.parseInt(s[i]);
Arrays.fill(dp, 1);
dp[1] = arr[0] >= arr[1] ? 1 : 2;
System.out.println(box());
}
static int box() {
int ret = -1;
for(int i=2; i<n; i++) {
for(int j=0; j<i; j++) {
if(arr[i] > arr[j])
dp[i] = Math.max(dp[i], dp[j]+1);
}
ret = Math.max(dp[i],ret);
}
return ret;
}
}
์ฑ๊ณต~