백준 2643. 색종이 올려놓기
https://www.acmicpc.net/problem/2643
2643번: 색종이 올려 놓기
첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다
www.acmicpc.net
이 문제는 Longest Increasing Sequence 랑 매우 흡사하다.
11053. 가장 긴 증가하는 부분수열
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인
tose33.tistory.com
우선 색종이를 올려놓을때, 아래에 이미 있는 사각형과 새롭게 올릴 사각형을 비교를 해야 한다.
비교는 두 사각형의 각각의 큰 변과, 각각의 작은 변을 비교하면 된다.
즉 아래에 있는 사각형의 큰 변 >= 새롭게 올릴 사각형의 큰 변 && 아래에 있는 사각형의 작은 변 >= 새롭게 올릴 사각형의 작은 변 을 만족하면 새롭게 올릴수 있는 사각형이다.
따라서 사각형을 저장할때 큰변, 작은변 순으로 저장하고 큰변기준 내림차순 정렬, 큰변이 같다면 작은변 기준 내림차순 정렬하면 된다.
d[i] = i 번째 사각형을 올렸을때 쌓아올린 최대 갯수
LIS 를 구할때 처럼 나보다 작은사각형들 중에서 가장 큰 d 값 + 1 이 된다.