본문 바로가기
PS/BOJ

[BOJ 1421] 나무꾼 이다솜

by Saerong2 2020. 5. 8.

 

 

문제 링크

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

 

1421번: 나무꾼 이다솜

첫째 줄에 이다솜이 가지고 있는 나무의 개수 N과 나무를 자를 때 드는 비용 C와 나무 한 단위의 가격 W이 주어진다. 둘째 줄부터 총 N개의 줄에 이다솜이 가지고 잇는 나무의 길이가 한 줄에 하나씩 주어진다. N은 1,000보다 작거나 같은 자연수이고, C와 W는 10,000보다 작거나 같은 자연수이다. 그리고 나무의 길이는 모두 10,000보다 작거나 같은 자연수이다.

www.acmicpc.net


아이디어

 

  • 나무가 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;
}

 

 

 

 

 

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

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

'PS > BOJ' 카테고리의 다른 글

[BOJ 14503] 로봇청소기  (0) 2020.05.15
[BOJ 14499] 주사위 굴리기  (0) 2020.05.14
[BOJ 1411] 비슷한 단어  (0) 2020.05.07
[BOJ 1564] 팩토리얼5  (0) 2020.05.04
[BOJ 1166] 선물  (0) 2020.04.30

댓글