문제 링크
https://www.acmicpc.net/problem/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; }
공부한 것을 정리하기 위한 기록입니다.
틀린 부분이 있다면 언제나 부드럽게 알려주세요.
'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 |
댓글