Problem Solving
boj 10571 : Diamonds
1ssrek
2016. 8. 26. 17:43
boj 10571 : Diamonds
https://www.acmicpc.net/problem/10571
LIS를 푸는 방법과 동일한 dp로 풀 수 있다.
1. d[i][0] , d[i][1] : 각각 다이아몬드의 무게, 선명도
2. a[i] : i번째까지의 최대길이의 부분수열
3. a[i] = max( a[j] ) + 1 (j 는 0 ~ i - 1 까지 d[j][0] < d[i][0] and d[j][1] > d[i][1] 을 만족하는 경우만을 고려)