백준 2643. 색종이 올려놓기

https://www.acmicpc.net/problem/2643

2643번: 색종이 올려 놓기

 

이 문제는 Longest Increasing Sequence 랑 매우 흡사하다.

https://tose33.tistory.com/18

11053. 가장 긴 증가하는 부분수열

 

우선 색종이를 올려놓을때, 아래에 이미 있는 사각형과 새롭게 올릴 사각형을 비교를 해야 한다.

비교는 두 사각형의 각각의 큰 변과, 각각의 작은 변을 비교하면 된다.

즉 아래에 있는 사각형의 큰 변 >= 새롭게 올릴 사각형의 큰 변 && 아래에 있는 사각형의 작은 변 >= 새롭게 올릴 사각형의 작은 변 을 만족하면 새롭게 올릴수 있는 사각형이다.

 

따라서 사각형을 저장할때 큰변, 작은변 순으로 저장하고 큰변기준 내림차순 정렬, 큰변이 같다면 작은변 기준 내림차순 정렬하면 된다.

 

d[i] = i 번째 사각형을 올렸을때 쌓아올린 최대 갯수 

LIS 를 구할때 처럼 나보다 작은사각형들 중에서 가장 큰 d 값 + 1 이 된다.