[BOJ] 7133 Milk and Honey

Table Of Contents

0. 들어가기

1. 문제 요약

1.1. 입력

M
D_M

H
D_H

N

이후
N
줄 동안
C
B

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; }