[AC] 2643 색종이 올려 놓기

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

정답 : https://github.com/stemp12/study/blob/master/acmicpc.net/2016.02/2643.cpp

얼핏보면 굉장히 어려운 문제 같다. 하지만 잘 보면 어렵지 않다.

dp인듯하지만 아주 기초적인 부분만 물어보고있다.

문제의 요점은 큰녀석이 가장 밑에 깔리고 점점 더 작은 녀석이 위로 올라가는데, 여기서 포인트는 겹점을 허용하고 있다는 말이다. 

먼저 전체 인풋을 정렬을 시킨 후에 현재 사각형이 얼마나 위에 올라오는지 차곡차곡 저장시킨다. 그리고 모든 사각형에 대해서 계속 최대값을 갱신하는 식으로 하면 가장 큰 값을 저장시킬수있다. 

그리고 마지막에 자기 자신을 올려주는 식으로 진행하면 된다.

그렇게 어렵지 않은 문제이다. 왜냐면 이건 초등부 문제이기 때문이다.