[BOJ] 7133 Milk and Honey

Table Of Contents

• 0. 들어가기
• 1. 문제 요약
  • 1.1. 입력
• 2. 풀이 정리
• 3. 구현

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. 풀이 정리

1. 어떤 들판에서 우유의 가치
   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]처럼 인덱싱 가능하도록 배열로 저장한다.
2. 어떤 들판에서 꿀의 가치
   H_{SUM}
   • 1번과 마찬가지로 구해준다.
3. 모든 들판
   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;
}