www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 이 문제는 전형적인 dp이면서 가장 긴 증가하는 배열을 구하면 된다. 기본 예제에서 확인해보자 3 7 5 2 6 1 4 여기서 가장 길게 증가하는 배열은 3 5 6이다 이 사이의 값들만 옮겨서 1 2 3 4 5 6 7로 바꾸어주면 된다. 3 5 사이로 4 3 밑으로 1, 2 6 뒤로 7 이렇게 되면 1, 2, 4 ,7만 옮기면 되기 때문에 4가된다. 그래서 이 문제는 가장 길면서 증가하는 배열의 수를 구한 다음 입력 ..

백준 11052 카드 구매하기 www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 카드 구매하기 문제의 경우 1장을 골랐을 때 최고의 가격, 2장을 골랐을 때의 최고의 가격 등을 구해주어서 문제를 해결할 수 있다. 아래의 예를 보자 10은 첫번째 카드, 9는 두번째 카드 ,,,, 쭉 진행한다. 1번째 카드의 경우 경우의 수가 1장 뿐이다. 2번째 카드 1 1, 2 자기 자체를 가지는 값 3번째 카드 1 2, 3 1번째 카드와 2번째 카드를 가졌을 때, 3번째 자기 자신..