Table Of Contents
0. 들어가기
1. 문제 요약
- 들판 개가 있고, 번째 들판은 소 마리 또는 벌 마리를 수용할 수 있다.
- 모든 소는 우유를, 벌은 꿀을 하나씩 생산한다.
- 한 들판에서, 첫 우유는 의 가치를 가지고, 다음 우유는 , 그 다음 우유는 의 가치를 가진다.
- 꿀도 마찬가지로 , , 처럼 가치가 하락한다.
- 가치는 0보다 작아지지 않는다.
- 들판 개에서 생산한 우유와 꿀의 가치가 최대일 때, 해당 가치를 출력하라.
1.1. 입력
이후 줄 동안
- : 첫 우유의 가치,
- : 감소하는 우유의 가치,
- : 첫 꿀의 가치,
- : 감소하는 꿀의 가치,
- : 들판의 수,
- : 어떤 들판이 수용할 수 있는 소의 수,
- : 어떤 들판이 수용할 수 있는 벌의 수,
2. 풀이 정리
- 어떤 들판에서 우유의 가치
- 해당 들판에서 키울 수 있는 소의 수는 이다.
- 소를 1마리 키운다면, 해당 들판에서 얻을 수 있는 우유의 총 가치는 이다.
- 소를 2마리 키운다면, 해당 들판에서 얻을 수 있는 우유의 총 가치는 이다.
- 소를 3마리 키운다면, 해당 들판에서 얻을 수 있는 우유의 총 가치는
M + (M - D_M) + (M - 2 * D_M)
이다.
- 따라서 소를 마리 키운다면, 은 부터 씩 줄여가면서 번 더하면 된다.
for i in C: M_SUM += M; M -= D_M
- 만약 중간에
M
이 음수가 된다면, 반복을 멈추거나 M = 0
처럼 처리해준다.
- 은 매 들판마다 구하지 않고, 미리 까지 구해
M_SUM[1000]
처럼 인덱싱 가능하도록 배열로 저장한다.
- 어떤 들판에서 꿀의 가치
- 모든 들판 개에 대해서, 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;
}