[BOJ] 7133 Milk and Honey

0. 들어가기

문제 링크 : https://www.acmicpc.net/problem/7133
정답 코드 : http://boj.kr/f4abf15e805f4f119d1cba3f7efe5a46

1. 문제 요약

들판 $N$ 개가 있고, $i$ 번째 들판은 소 $C_{i}$ 마리 또는 벌 $B_{i}$ 마리를 수용할 수 있다.
모든 소는 우유를, 벌은 꿀을 하나씩 생산한다.
- 한 들판에서, 첫 우유는 $M$ 의 가치를 가지고, 다음 우유는 $M - D_{M}$ , 그 다음 우유는 $M - 2 * D_{M}$ 의 가치를 가진다.
- 꿀도 마찬가지로 $H$ , $H - D_{H}$ , $H - 2 * D_{H}$ 처럼 가치가 하락한다.
- 가치는 0보다 작아지지 않는다.
들판 $N$ 개에서 생산한 우유와 꿀의 가치가 최대일 때, 해당 가치를 출력하라.

1.1. 입력

$M$ $D_{M}$
$H$ $D_{H}$
$N$
이후 $N$ 줄 동안 $C$ $B$

$M$ : 첫 우유의 가치, $0 \leq M \leq 1000$
$D_{M}$ : 감소하는 우유의 가치, $0 \leq D_{M} \leq M$
$H$ : 첫 꿀의 가치, $0 \leq M \leq 1000$
$D_{H}$ : 감소하는 꿀의 가치, $0 \leq D_{H} \leq H$
$N$ : 들판의 수, $1 \leq N \leq 1000$
$C$ : 어떤 들판이 수용할 수 있는 소의 수, $1 \leq C \leq 100$
$B$ : 어떤 들판이 수용할 수 있는 벌의 수, $1 \leq B \leq 100$

2. 풀이 정리

어떤 들판에서 우유의 가치 $M_{S U M}$ $M_{S U M}$
- 해당 들판에서 키울 수 있는 소의 수는 $C$ 이다.
- 소를 1마리 키운다면, 해당 들판에서 얻을 수 있는 우유의 총 가치는 $M$ 이다.
- 소를 2마리 키운다면, 해당 들판에서 얻을 수 있는 우유의 총 가치는 $M + (M - D_{M})$ 이다.
- 소를 3마리 키운다면, 해당 들판에서 얻을 수 있는 우유의 총 가치는 $M + (M - D_{M}) + (M - 2 * D_{M})$ 이다.
- 따라서 소를 $C$ $C$ 마리 키운다면, $M_{S U M}$ $M_{S U M}$ 은 $M$ $M$ 부터 $D_{M}$ $D_{M}$ 씩 줄여가면서 $C$ $C$ 번 더하면 된다.
  - for i in C: M_SUM += M; M -= D_M
  - 만약 중간에 M이 음수가 된다면, 반복을 멈추거나 M = 0처럼 처리해준다.
  - $M_{S U M}$ 은 매 들판마다 구하지 않고, 미리 $C = 1000$ 까지 구해 M_SUM[1000]처럼 인덱싱 가능하도록 배열로 저장한다.
어떤 들판에서 꿀의 가치 $H_{S U M}$ $H_{S U M}$
- 1번과 마찬가지로 구해준다.
모든 들판 $N$ $N$ 개에 대해서, max(우유의 가치, 꿀의 가치)를 결과값에 더해주면 된다.
- for i in N: ans += max(M_SUM[i], H_SUM[i])

3. 구현

#include <iostream>
using namespace std;

int M, D_M, H, D_H, N;
int M_SUM[1005], H_SUM[1005];
int ans;

int main()
{
	cin >> M >> D_M;
	cin >> H >> D_H;
	cin >> N;

	M_SUM[1] = M;
	H_SUM[1] = H;

	for (int i = 2; i <= 1000; i++) {
		M = max(M - D_M, 0);
		M_SUM[i] = M_SUM[i - 1] + M;

		H = max(H - D_H, 0);
		H_SUM[i] = H_SUM[i - 1] + H;
	}

	while (N--) {
		int C, B;
		cin >> C >> B;

		ans += max(M_SUM[C], H_SUM[B]);
	}

	cout << ans;

	return 0;
}