[Jungol] 정올 2194 요플레 공장

출처: http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1454

Approach

문제에서 해당 주차에 필요한 우유의 양과 구매 금액이 주어집니다.

해당 주차에 필요한 양이므로 해당 양을 그 전에 구입해도 무방하지만

구매 비용과 보관 비용을 최소화하고자 합니다.

Q) 3주차에 필요한 양을 구매할 때 고려사항

- 1주차에 구매해서 2주 보관

- 2주차에 구매해서 1주 보관

- 3주차 구매

 

Q) 4주차에 필요한 양을 구매할 때 고려사항

- 1주차에 구매해서 3주 보관

- 2주차에 구매해서 2주 보관

- 3주차에 구매해서 1주 보관

- 4주차 구매

위와 같은 패턴으로 각 주차별로 계산할 수도 있겠지만 복잡.

 

시뮬레이션

① 1주차에는 비교데이터가 없으므로 필요한 양만큼 구매 합니다.

 

② 2주차는 지난 1주차에서 구매해서 1주일 보관한 것이 효율적인지

    2주차 당시에 필요한 양을 구매하는 것이 좋은지 비교합니다.

    → 89 vs 88+5 → 89원으로 1주차때 구매하지 않고 2주차에 필요한 양을 구매하는 것이 이득입니다.

 

③ 3주차에서는 아래와 같이 고려할 수 있습니다.

    → 1주차에 구매해서 2주 보관 vs 2주차에 구매해서 1주 보관 vs 3주차 구매

    하지만 『1주차 구매해서 2주 보관』 하는 경우는 고려하지 않아도 됩니다.

    왜냐하면 2주차때 그것을 고려해서 선택한 금액이 89원이기 때문입니다.

    즉, 2주차 당시 1주차에 구매해서 보관하는 것이 비효율적인 것을 알아내어 반영된 것입니다.

    따라서 3주차에서 지난 2주차에 구매했었던 비용 89원만 고려합니다.

    → 97 vs 89 + 5 → 94으로 지난 2주차에 구매해서 1주일 보관하는 것이 이득입니다.

④ 4주차에서 고려사항 = 4주차때 구매할 것인지 3주차때 선택금액으로 구매해서 1주일 보관할 것인지 비교

    → 91 vs 94 + 5 → 91로 4주차에 필요한 우유를 구매하는 것이 이득.

※ 구매 금액의 합이 int 범위를 벗어나므로 long long 타입

 

if) 1주차 구매 금액이 1원인 경우에는 아래와 같이 변경됩니다.

▶ 해당 주차에 구매금액 vs (지난주에 선택한 금액 + 보관 비용)을 비교해서 저렴한 금액을 선택해야 합니다.

 

---

#include <stdio.h>
 
typedef long long LL;
const int MAX_N = 10000 + 5;
int N, S;
LL ans;
int C[MAX_N], Y[MAX_N];
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &S);
 
    for (int i = 1; i <= N; ++i) {
        scanf("%d %d", &C[i], &Y[i]);
    }
 
    // 1주차
    ans = C[1] * Y[1];
    int cost = C[1];
 
    // 2~N주차
    for (int i = 2; i <= N; ++i) {
        cost = C[i] < cost + S ? C[i] : cost + S;
        ans += Y[i] * cost;
    }
 
    printf("%lld\n", ans);
}
#include <stdio.h>
 
typedef long long LL;
const int MAX_N = 10000 + 5;
int N, S;
LL ans;
int C[MAX_N], Y[MAX_N];
int main() {
    // freopen("input.txt", "r", stdin);
    scanf("%d %d", &N, &S);
 
    for (int i = 1; i <= N; ++i) {
        scanf("%d %d", &C[i], &Y[i]);
    }
 
    // 1주차
    ans = C[1] * Y[1];
    int cost = C[1];
 
    // 2~N주차
    for (int i = 2; i <= N; ++i) {
        cost = C[i] < cost + S ? C[i] : cost + S;
        ans += Y[i] * cost;
    }
 
    printf("%lld\n", ans);
}