[BOJ 1421] 나무꾼 이다솜

 

 

문제 링크

https://www.acmicpc.net/problem/1421

1421번: 나무꾼 이다솜

---

아이디어

 

• 나무가 1,000개 이하 ,나무의 길이가 10,000 이하이기 때문에
  나무를 자르는 단위를 1부터 10,000까지 완전탐색 해도 시간 안에 해결할 수 있다.
  
  
• 가지고 있는 나무 중에서 가장 긴 나무의 길이를 maximum값으로 하여 완전탐색하여도 된다.

---

주의할 점

 

• N = 1,000 , C = 1, W = 10,000 , 모든 나무의 길이가 10,000일 경우
  int자료형으로 ans를 계산하면 overflow가 발생한다.
  
  
• 버는 돈보다 자르는 비용이 더 든다면, 자르지 않는게 이득이다.

---

소스코드

#include <cstdio>
#include <algorithm>
using namespace std;

int main()
{
    int n, c, w, tree[1001];
    scanf("%d %d %d", &n, &c, &w);
    for (int i = 0; i < n; ++i)
        scanf("%d", tree + i);

    long long int ans = 0, margin;
    int cost, cnt, t_margin;
    for (long long unit = 1; unit <= 10000; ++unit) {
        margin = 0;
        for (int i = 0; i < n; ++i) {
            cnt = tree[i] / unit;
            cost = (tree[i] - 0.5) / unit;
            t_margin = unit * cnt * w - c * cost;
            if (t_margin > 0)
                margin += t_margin;
        }
        ans = max(ans, margin);
    }
    printf("%lld\n", ans);
    return 0;
}

 

 

 

 

 

공부한 것을 정리하기 위한 기록입니다.

틀린 부분이 있다면 언제나 부드럽게 알려주세요.