그리디

https://www.acmicpc.net/problem/23845시간 제한메모리 제한1초1024MB문제인형 수집가 하령이에게는 N개의 속이 비어있는 인형이 있다. 각각의 인형은 크기는 Xi이다. 인형의 속은 비어있기 때문에 그 안에 또 다른 인형을 넣을 수 있고, 크기가 서로 다른 인형들을 조합해서 마트료시카를 만들 수 있다. 정확히는 가장 큰 인형의 크기를 Q, 가장 작은 인형의 크기를 W, 인형의 개수를 T라고 할 때, (Q - W + 1 = T)를 만족하는 인형의 집합을 마트료시카라고 하자. 마트료시카는 1개의 인형으로 구성될 수도 있음에 유의하라. 하나의 마트료시카의 가격은 Q × T로 책정된다고 한다. 하령이는 가지고 있는 인형을 적절히 조합하여 마트료시카들을 구성해서 최대의 수익을 올리고 싶..

시간 제한메모리 제한1초512MB문제취준생 주헌이는 드디어 취업에 성공했다. 주헌이가 취직한 회사는 비대면 전자계약 서비스 모두싸인(MODUSIGN) 이라는 회사이다. 그리고 오늘은 첫 출근날이다. 주헌이의 출근길에는 다리가 있는데, 전날에 비가 많이 오는 바람에 다리가 끊어져 판자 여러 개로 쪼개져 버렸다. 주헌이는 무사히 회사에 도착할 수 있을까? 다리는 수직선으로 나타낼 수 있으며, 각 판자는 구간 [ L, R ]의 범위에 놓여 있다. 주헌이는 0에서 출발하여 오른쪽(양의 방향)으로만 이동한다. 판자로 덮인 좌표는 자유롭게 건너갈 수 있다. 하지만 판자로 덮이지 않은 좌표는 오직 주헌이가 점프를 해야만 건너갈 수 있으며, 점프를 할 경우 착지한 위치에 판자가 놓여 있어야 한다. 판자의 양 끝점에도 ..