Yukicoder No. 31 悪のミックスジュース

Yukicoder No. 31 악의 믹스 주스

문제 링크

 

문제

믹스 주스가 다 떨어졌습니다.

믹스 주스의 원재료표시는, 차례대로 과일 $1$, 과일 $2$, $\cdots$, 과일 $N$입니다.

각 과일의 100% 주스를 섞어서 믹스 주스를 $V$리터 만들려고 합니다.

100% 과일 $k$ 주스는 $1$리터들이 한 팩에 $C_k$엔입니다.

$V$ 리터 믹스 주스를 원재료표시의 변경 없이 만들기 위한 최소 비용을 구하는 프로그램을 작성해주세요.

즉, 믹스 주스에 대해서 과일 $k$가 들어간 비율 $p_k$는 $p_1 \ge p_2 \ge \cdots \ge p_N$이 되어야 합니다. 또한, 사용하지 않는 과일이 있어서는 안 됩니다.

$1$리터 팩을 사서, 그 일부만 사용하는 것도 가능합니다.

 

입력

$1$번째 줄에, 과일의 종류 수를 의미하는 정수 $N \ (1 \le N \le 100)$과 만들고 싶은 믹스 주스의 양 $V \ (1 \le V \le 10^9)$가 주어집니다.

$2$번째 줄에, 100% 과일 $k$ 주스 $1$ 리터 팩의 가격을 의미하는 정수 $C_k \ (1 \le C_k \le 10^9)$가 공백으로 구분되어 주어집니다.

출력

최소 비용 (단위는 엔)을 의미하는 정수를 $1$번째 줄에 출력해주세요.

마지막에 개행문자를 넣어주세요.

예제 설명

1. 과일 $1$을 $8$리터, 과일 $2, 3$을 각각 $1$리터씩 섞는 것이 최적입니다.
2. 과일 $1$을 $5$리터, 과일 $2$를 $4$리터, 과일 $3$을 $1$리터 섞는 것이 최적입니다.
3. 과일 $1$을 $4$리터, 과일 $2$를 $3$리터, 과일 $3$을 $3$리터 섞는 것이 최적입니다.
4. 예를 들어, $3$종류의 과일 $1$리터 팩을 하나씩 사서, 과일 $1$을 $0.5$리터, 과일 $2$를 $0.3$리터, 과일 $3$을 $0.2$리터씩 섞는 것이 가능합니다.
5. 답이 $2^{32}$를 넘을 수 있음에 주의해주세요. 과일 $1, 2$를 각각 $7$리터, 과일 $3, 4, 5$를 각각 $6$리터, 과일 $6, 7, 8, 9$를 각각 $1$리터 섞는 것이 최적입니다.

풀이

우선, 모든 과일이 들어가 있어야 한다는 조건 때문에, 모든 과일 주스를 한 팩씩 구매합시다.

$V$가 $N$만큼 줄어들고, 가격이 $C_1 + \cdots + C_N$만큼 더 드는 상황에서, 모든 과일을 한 팩씩 구매해야한다는 조건 없이 문제를 해결할 수 있습니다.

우리는 과일의 비율에 대한 조건 $p_1 \ge p_2 \ge \cdots \ge p_N \ge 0$을 다른 방식으로 생각해 볼것입니다.

모든 과일은 적어도 $p_N$ 리터만큼 구매해야 합니다. 그러므로, 이는 과일 $1, \cdots, N$ 전부를 섞은 $N$ 리터짜리 주스를 $p_N$ 개만큼 구매하는 것과 마찬가지입니다.

이제, 과일 $1, 2, \cdots, N-1$를 $p_1 - p_N, p_2 - p_N, \cdots, p_{N-1}-p_N$만큼 섞어야 합니다.

모든 과일을 추가로 $p_{N-1} - p_N$ 리터만큼 구매해야 합니다. 그러므로, 이는 과일 $1, \cdots, N-1$ 전부를 섞은 $N-1$ 리터 짜리 주스를 $p_{N-1} - p_N$ 개만큼 구매하는 것과 마찬가지입니다.

이런 식으로, 우리는 과일 $1, \cdots, k$ 전부를 섞은 주스를 $p_{k-1} - p_k$ 개만큼 구매하는 것으로 문제를 바꿀 수 있습니다.

이러한 경우에 이점은, 제한 조건이 $p_{k-1}-p_k \ge 0$뿐이라는 것입니다.

 

결국, 문제를 다음과 같이 바꿀 수 있습니다.

• $N$ 종류의 음료 팩이 있습니다.
• $k$ 번째의 음료 팩은 용량이 $k$ 리터이고, 가격은 $C_1 + \cdots + C_k$입니다.
• 이 음료 팩을 적당히 사서, 용량이 $V-N$ 리터가 되도록 할 때, 최소 가격을 구해주세요.

이제 이 문제를 해결해 봅시다.

• $V$가 작을 경우에는, 동적 계획법 문제로 $O(NV)$에 해결할 수 있습니다.
• 각 음료 팩을 임의의 양의 실수만큼 구매할 수 있으면, 각 음료팩 중에 가장 $1$리터당 가격이 싼, 즉 $\dfrac{C_1 + \cdots + C_k}{k}$가 가장 작은 팩을 사는 게 가장 좋아 보입니다.

우리는 이 두 접근을 섞을 것입니다. 가장 $1$리터당 가격이 싼 음료 팩이 $a$ 번째라고 해봅시다. 그러면, $a$가 아닌 다른 음료 팩 $b$는 $a$ 개 이상 살 필요가 없습니다.

왜냐하면, 음료팩 $b$를 $a$ 개 사서 $ab$ 리터를 만드는 것보다, 음료팩 $a$를 $b$ 개 사서 $ab$ 리터를 만드는 것이 가격이 더 싸기 때문입니다.

가장 극단적인 경우인, $a = N$이고 모든 음료 팩을 $N-1$ 개 구매해도, 최대 $\dfrac{N^3-N}{2}$ 리터만큼의 음료를 제외하고는, 모두 다 $a$ 번째 음료 팩만 구매하면 됩니다.

$\dfrac{N^3-N}{2}$ 리터가 넘는 부분은 $a$ 번째 음료 팩을, 나머지는 동적 계획법으로 최적의 답을 찾아주면 됩니다. 시간복잡도는 $O(N^4)$ 입니다.

 

코드: https://yukicoder.me/submissions/733682