[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 \le M \le 1000
D_M
: 감소하는 우유의 가치,
0 \le D_M \le M
H
: 첫 꿀의 가치,
0 \le M \le 1000
D_H
: 감소하는 꿀의 가치,
0 \le D_H \le H
N
: 들판의 수,
1 \le N \le 1000
C
: 어떤 들판이 수용할 수 있는 소의 수,
1 \le C \le 100
B
: 어떤 들판이 수용할 수 있는 벌의 수,
1 \le B \le 100

2. 풀이 정리

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