1421번 나무꾼 이다솜(C++)

공부를 합시다..c 다 까먹겠네

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

1421번: 나무꾼 이다솜

문제

이다솜은 나무꾼이다. 이다솜은 산신령이 준 금도끼와 은도끼를 이용해서 나무를 열심히 했다. 나무가 끝난 후에 나무들을 쳐다보면서 내가 왜 나무를 하면서 살까 생각하다가, 나무가 엄청나게 값어치가 있다는 것을 알고 나무를 팔러 시장에 가기로 했다.

지역 목재상에서 이다솜의 나무를 사려고 했지만, 너무 길이가 제멋대로여서 나무를 사는 것을 거절을 했다. 목재상의 조건은 일단 팔려고 하는 나무의 길이를 전부 같게 만들어 오라는 것이었다. (나무의 길이는 자연수로) 이다솜은 나무를 하나씩 여러 번 팔려고 했지만, 지역 목재상의 주인은 한 사람에게 평생 단 한번의 판매 기회를 제공하다고 했기 때문에, 이다솜은 근처 작업장으로 가서 나무를 자르기로 했다.

작업장에서 나무를 한 번 자를 때는, C원이 든다. 그리고, 지역 목재상에서 나무를 살 때는, 한 단위에 W원씩 준다. (다른 말로 하면, K개의 나무가 있고, 길이가 L이면, 이다솜은 K*L*W원을 벌 수 있다.)

이다솜이 현재 가지고 있는 나무의 길이가 주어졌을 때, 이다솜이 벌 수 있는 가장 큰 돈을 구하는 프로그램을 작성하시오.

사전지식

동적 배열 선언: c++에서는 new 연산자와 delete 연산자를 사용한다.

 

int length;

std::cin >> length;

int* arr = new int[length];

 

마치 c에서 malloc과 free를 쓴 것과 같은 이치이다.

해결과정

https://velog.io/@lee02g29/자바-8-백준-실버1-1421번-낚시꾼-이다솜

[자바 8] 백준 실버1 - 1421번, 낚시꾼 이다솜

이 분의 자바 코드를 보고 영감을 얻어서 c++로 작성을 하였다.

정리하자면,

1. 단위 크기로 자르는데, 이 단위 크기의 값은 1부터 ~ 가장 길이가 긴 나무의 길이 값까지 for문으로 순회한다. (변수 j)

 

2. 한 단위 크기에 대해, 이제 각 나무 별로 그 단위 크기로 한 번 잘라본다.

이 때 cnt(자른 횟수)가 중요한데, 나무 길이가 10일 때 단위 크기가 5라고 해보자. 그렇다면 cnt는 2가 아닌 1이다.

(10 / 5 - 1 = 1)

나무 길이가 10일 때 단위 크기가 3이라고 해보자. 그렇다면 cnt는 3이다.

(10 / 3 = 3 ... 1)

나무 길이가 10일 때 단위 크기가 10이라고 해보자. 그렇다면 cnt는 0이다.

(10 / 10 - 1 = 0)

나무 길이가 10일 때 단위 크기가 100이라고 해보자. 그렇다면 cnt는 0이다.

(10 / 100 = 0 ...10)

 

결론적으로 나머지가 0이 되면 1을 빼주고, 나머지가 있으면 1을 빼지 않으면 된다.

 

3. 각 나무에 대한 수익 공식이야 유도하는 건 어렵지 않았다.

수익 = 한 단위의 가격(w) * 단위 크기(j) * 나무조각개수 - 자른 횟수(cnt) * 한 번 자르는 비용(c)

이 때 한 나무에 대해서 수익이 마이너스면 최종 수익에서 제외해야 한다. 즉 그 한 나무는 안 팔기로 하고 버려야 한다. 예를 들어서 한 나무에 대한 수익이 -998이 나왔다. 이 나무는 그냥 안 팔기로 하면 된다. 이걸 놓쳐서 한참 헤맸다... 백준 질문에 누가 반례를 올려주었길래 이거 덕분에 문제를 찾아서 해결했다. 안되시는 분은 아래 반례 꼭 해보시길...

4 1000 1

2 1 1 1

 

4. 곱셈이 너무 많아서 단위가 int를 넘어갈 것 같으면 안전하게 long long 자료형 선언하기

코드

#include <iostream>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    long long N, C, W;
    long long tree;

    long long max = 0;


    cin >> N >> C >> W;

    long long* arr = new long long[N];
    long long ans = 0;

    for (int i = 0; i < N; i++) {
        cin >> tree;
        arr[i] = tree;
        if (tree >= max) max = tree;
    }

    // j는 자르는 단위의 크기
    for (int j = 1; j <= max; j++) {
        long long sum = 0;

        for (int k = 0; k < N; k++) {
            long long cnt = 0; // 자른 횟수
            if (arr[k] >= j) {

                if (arr[k] % j == 0) cnt = arr[k] / j - 1;
                else cnt = arr[k] / j;

                long long temp = W * j * (arr[k] / j) - cnt * C;
                if(temp>0) sum += temp;
            }
        }
        if (sum >= ans) ans = sum;
    }

    cout << ans;

    delete[] arr;
    return 0;
}

결과