[SWExpertAcademy] 3987번 쉬운 벌꿀채취 C++

"2115. [모의 SW 역량테스트] 벌꿀채취"에 기반을 두는 문제.

 

문제 : N개의 벌통이 있는데, 각 벌통에 있는 꿀의 양으로 부터 벌꿀을 채취해 얻을 수 있는 최대 수익 알아내기

<벌꿀채취 과정>

1. 꿀은 최대 C까지만 채취 가능

2. 서로 다른 벌통에서 채취한 꿀이 섞이지 않도록 하나의 벌통에서 채취한 꿀은 하나의 용기에 담기

3. 하나의 벌통에서 꿀 채취할 때, 한 번에 모든 꿀을 채취

4. 채취한 꿀을 팔 때, 하나의 용기 속 꿀의 양이 많을수록 상품가치가 높고 각 용기의 꿀 양을 제곱만큼 수익 발생

    ex) 6, 1, 8 만큼 꿀이 담긴 용기 3개를 판매하면 (6*6) + (1*1) + (8*8) = 36 + 1 + 64 = 101 수익이 생김

 

- 입력

테스트 케이스 개수 T

   T줄 - 벌통 크기 N, 꿀 채취 최대 양 C

      N개 - 벌통에서 채취할 수 있는 꿀의 양

 

- 출력

꿀 채취 후 얻는 최대 수익

 

- 제약사항

1 ≤ N ≤ 50, 1 ≤ C ≤ 10^5

1 ≤ N ≤ 20, 1 ≤ C ≤ 10^9

벌통 꿀의 양 ≤ C

---

문제 이해

즉, 꿀이 들어있는 칸 N개 중에서 조합을 뽑아서 그 조합이 C를 넘지 않도록 하고 최대의 수익을 낼 수 있도록 하자!

 

접근 방법

DFS를 사용해서 채취할 꿀통들의 조합을 찾고, 찾은 조합들 중에서 최대의 돈을 구한다.

 

코드

시도1) vector 사용으로 인해 통과X

#include <iostream>
#include <cmath>
#include <vector>
using namespace std;

int T; 
int N, C;
int amount[51];

int visited[51];
vector<int> path;
int maxMoney = -21e8;

int howMuch(vector<int> path) {
    int sum = 0;
    for (int i = 0; i < path.size(); i++)
        sum += (amount[path[i]]* amount[path[i]]);

    return sum;
}

void getHoney(int now, int level, int limit) {

    if (level == N)
        return;

    if (level != 0  && limit >= 0) {
        //디버깅 출력용
        //cout << "limit: " << limit << endl;
        //for (int i = 0; i < level; i++)
        //    cout << path[i] << ' ';
        //cout << endl;
        int money = howMuch(path);
        if (money > maxMoney)
            maxMoney = money;
    }

    for (int i = now; i < N; i++) {

        if (visited[i] != 0)
            continue;

        visited[i] = 1;
        path.push_back(i);

        getHoney(i + 1, level + 1,  limit - amount[i]);

        visited[i] = 0;
        path.pop_back();

    }
}

int main() {
    cin >> T;
    for (int t = 1; t <= T; t++) {
        
        cin >> N >> C;
        for (int n = 0; n < N; n++) {
            cin >> amount[n];
        }

        getHoney(0, 0, C);

        if (maxMoney == -21e8) {
            for (int i = 0; i < N; i++) {
                int tmpMoney = amount[i] * amount[i];
                if (amount[i] <= C && tmpMoney > maxMoney)
                    maxMoney = tmpMoney;
            }
        }
        cout << "#" << t << " " << maxMoney << '\n';
    }
}

vector로 사용하고 있던 path는 int 배열로 변경

 

시도2) Fail (제한시간 초과) - 10개 중 2개 정답

#include <iostream>
using namespace std;

int T; 
int N, C;
int amount[51];

int visited[51];
int path[51];
int maxMoney = -21e8;

int howMuch(int hist[51], int lev) {
    int sum = 0;
    for (int i = 0; i < lev; i++)
        sum += (amount[path[i]]* amount[path[i]]);

    return sum;
}

void getHoney(int now, int level, int limit) {

    if (level == N)
        return;

    if (level != 0  && limit >= 0) {
        int money = howMuch(path, level);
        if (money > maxMoney)
            maxMoney = money;
    }

    for (int i = now; i < N; i++) {

        if (visited[i] != 0)
            continue;

        visited[i] = 1;
        path[level] = i;

        getHoney(i + 1, level + 1,  limit - amount[i]);

        visited[i] = 0;
        path[level] = -1;

    }
}

int main() {
    cin >> T;
    for (int t = 1; t <= T; t++) {
        
        cin >> N >> C;
        for (int n = 0; n < N; n++) {
            cin >> amount[n];
        }

        getHoney(0, 0, C);

        if (maxMoney == -21e8) {
            for (int i = 0; i < N; i++) {
                int tmpMoney = amount[i] * amount[i];
                if (amount[i] <= C && tmpMoney > maxMoney)
                    maxMoney = tmpMoney;
            }
        }
        cout << "#" << t << " " << maxMoney << '\n';
    }
}

뭐가 문제일까 고민하다가 제곱 계산으로 인해 int 범위를 넘어갈 수도 있다는 생각이 들어서 제곱 계산이 들어가는 변수들을 모두 long long으로 변경.

 

시도3) Fail (제한시간 초과) - 10개 중 2개 정답

#include <iostream>
using namespace std;

int T; 
int N, C;
int amount[51];

int visited[51];
int path[51];
long long maxMoney = -21e8;

long long howMuch(int hist[51], int lev) {
    long long sum = 0;
    for (int i = 0; i < lev; i++)
        sum += (amount[path[i]]* amount[path[i]]);

    return sum;
}

void getHoney(int now, int level, int limit) {

    if (level == N)
        return;

    if (level != 0  && limit >= 0) {
        int money = howMuch(path, level);
        if (money > maxMoney)
            maxMoney = money;
    }

    for (int i = now; i < N; i++) {

        if (visited[i] != 0)
            continue;

        visited[i] = 1;
        path[level] = i;

        getHoney(i + 1, level + 1,  limit - amount[i]);

        visited[i] = 0;
        path[level] = -1;

    }
}

int main() {
    cin >> T;
    for (int t = 1; t <= T; t++) {
        
        cin >> N >> C;
        for (int n = 0; n < N; n++) {
            cin >> amount[n];
        }

        getHoney(0, 0, C);

        if (maxMoney == -21e8) {
            for (int i = 0; i < N; i++) {
                long long tmpMoney = amount[i] * amount[i];
                if (amount[i] <= C && tmpMoney > maxMoney)
                    maxMoney = tmpMoney;
            }
        }
        cout << "#" << t << " " << maxMoney << '\n';
    }
}

가지치기를 더 해줘야 할 것 같은데... 사실 숫자들의 모든 조합을 path로 만들어서 money 계산을 하지 않고 큰 숫자들부터 C를 넘지 않는 조합을 먼저 찾으면 될텐데...

고민1. amount에 있는 숫자들을 정렬하 가장 처음으로 C를 넘지 않도록 만들어지는 조합이 최대 money일까?

고민2. path들을 따로 다 저장해서 그 합이 가장 큰 녀석을 찾을까? -> 이건 기존 복잡도랑 동일할 것 같은데

- - - 아직 해결하지 못한 문제 - - -

 

출처 : https://swexpertacademy.com/main/code/userProblem/userProblemDetail.do?contestProbId=AWIakQe6tToDFAVH 

SW Expert Academy