BOJ 1421 - 나무꾼 이다솜 링크
(2023.08.07 기준 S2)

문제

N개의 나무가 있다. 나무의 길이를 전부 같게 만들어서 팔고자 한다.
나무를 1번 자를 때 C원이 들고, 길이가 L개이고 나무가 K개가 있다면 K×C×W원을 받을 수 있다.
이 때, 가장 많이 벌 수 있는 돈 출력

알고리즘

나무의 길이가 최대 10,000이므로 브루트포스

풀이

나무의 길이를 잘 보자.
만약, 나무의 길이를 L로 나눴을 때, 나머지가 생긴다면 자르는 횟수는 몫이 된다.
하지만, 나머지가 생기지 않는다면 자르는 횟수는 몫-1이 된다.

그리고 만약에 자르는 비용이 단위의 가격보다 터무니 없이 비쌀 수 있다. 이런 경우에는 당연히 팔지 않는 것이 이득이다.

위 두 경우만 생각하면서 1~10000까지의 길이에 따른 벌 수 있는 돈을 계산하여 최댓값을 구하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int N, C, W; cin >> N >> C >> W;
    int tree[N]; for (int i = 0; i < N; i++) cin >> tree[i];

    // 나무 하나를 L의 길이가 나오게 자르면 q개 및 나머지 길이 r이 나온다.
    // 나머지 길이가 있다면 q번 잘라야 하며, 나머지 길이가 없다면(딱 맞게 잘린다면) (q-1)번 잘라야 한다.
    // 팔지 않는 것이 이득일 수 있음을 알아야 한다.
    ll answer = 0;
    for (int L = 1; L <= 10000; L++){ // 1부터 10000까지의 길이에 따른 벌 수 있는 돈을 전부 구해보자.
        ll result = 0;
        for (int i = 0, q, r; i < N; i++){
            q = tree[i] / L; r = tree[i] % L;
            result += max(0, r ? (q * L * W - q * C) : (q * L * W - (q - 1) * C));
        }
        answer = max(answer, result);
    }

    cout << answer;
}

• Python

import sys; input = sys.stdin.readline

N, C, W = map(int, input().split())
tree = [int(input()) for _ in range(N)]

# 나무 하나를 L의 길이가 나오게 자르면 q개 및 나머지 길이 r이 나온다.
# 나머지 길이가 있다면 q번 잘라야 하며, 나머지 길이가 없다면(딱 맞게 잘린다면) (q-1)번 잘라야 한다.
# 팔지 않는 것이 이득일 수 있음을 알아야 한다.
answer = 0
for L in range(1, 10001): # 1부터 10000까지의 길이에 따른 벌 수 있는 돈을 전부 구해보자.
    result = 0
    for i in range(N):
        q, r = divmod(tree[i], L)
        result += max(0, (q * L * W - q * C) if r else (q * L * W - (q - 1) * C))
    answer = max(answer, result)

print(answer)