[모의 SW 역량테스트] 2115. 벌꿀채취

[모의 SW 역량테스트] 벌꿀채취

---

1. 이해하기

• 벌통에 있는 꿀을 두 명의 일꾼이 채취한다.

  • 일꾼은 꿀을 채취할 수 있는 벌통의 수 M이 주어질 때, 각각의 일꾼은 가로로 연속되도록 M개의 벌통을 선택하고 선택한 벌통에서 꿀을 채취할 수 있다.

  • 각 일꾼이 선택한 벌통이 겹치면 안 된다.

  • 두 명의 일꾼은 선택한 벌통에서 꿀을 채취하여 용기에 담아야 한다. 이 때, 용기는 각각의 일꾼이 하나씩 가지고 있는 것이다. 벌통에 채취할 수 있는 꿀의 최대 양은 C이다.

  • 최대 C보다 더 많이 채울 수 없다.

• 두 일꾼이 꿀을 채취하여 얻을 수 있는 수익의 합이 최대가 되는 경우를 찾는 문제.

• 채취가능한 모든 경우를 해보는 완전탐색 문제.

---

2. 구현하기

• 벌통에 있는 꿀을 두 명의 일꾼이 채취한다.

  • 각 일꾼들이 채취한 꿀의 위치가 같은 행에 놓여있는지 검사하고 맞을때, 수익의 최댓값을 구한다.

  bool is_all_same_row(vector<Point>& worker) {
      int size = worker.size();
      int x = worker[0].x;
      for(int i = 0; i < size; i++) {
          if(x != worker[i].x) return false;
      }
      return true;
  }
  
  int solve(vector<Point>& f_worker, vector<Point>& s_worker) {
      vector<int> chosen;
      int ret = 0;
      for(int i = 0; i <= N*N-M; i++) {
          for(int j = 0; j < M; j++) {
              f_worker.push_back({(i+j)/N,(i+j)%N});
          }
          for(int j = i+M; j <= N*N-M; j++) {
              for(int k = 0; k < M; k++) {
                  s_worker.push_back({(j+k)/N,(j+k)%N});
              }
              if(is_all_same_row(f_worker) and is_all_same_row(s_worker)) {
                  int f = get_max(0,f_worker,chosen);
                  int s = get_max(0,s_worker,chosen);
                  ret = max(ret,f+s);
              }
              for(int k = 0; k < M; k++) {
                  s_worker.pop_back();
              }
          }
          for(int j = 0; j < M; j++) {
              f_worker.pop_back();
          }
      }
      return ret;
  }

• 각 일꾼들이 채취한 꿀의 최대 수익을 구한다.

  int get_max(int index, vector<Point>& worker, vector<int>& chosen) {
      if(index == M) {
          int sum = 0;
          int ret = 0;
          for(int i = 0; i < (int)chosen.size(); i++) {
              Point now = worker[chosen[i]];
              sum += map[now.x][now.y];
              ret += map[now.x][now.y]*map[now.x][now.y];
          }
          if(sum > C) return 0;
          else return ret;
      }
  
      int ret = 0;
      chosen.push_back(index);
      ret = max(ret,get_max(index+1,worker,chosen));
      chosen.pop_back();
      ret = max(ret,get_max(index+1,worker,chosen));
      return ret;
  }

---

3. 전체 코드

#include <iostream>
#include <vector>
using namespace std;
struct Point{
    int x,y;
};
int map[10][10];
int N,M,C;

int get_max(int index, vector<Point>& worker, vector<int>& chosen) {
    if(index == M) {
        int sum = 0;
        int ret = 0;
        for(int i = 0; i < (int)chosen.size(); i++) {
            Point now = worker[chosen[i]];
            sum += map[now.x][now.y];
            ret += map[now.x][now.y]*map[now.x][now.y];
        }
        if(sum > C) return 0;
        else return ret;
    }

    int ret = 0;
    chosen.push_back(index);
    ret = max(ret,get_max(index+1,worker,chosen));
    chosen.pop_back();
    ret = max(ret,get_max(index+1,worker,chosen));
    return ret;
}

bool is_all_same_row(vector<Point>& worker) {
    int size = worker.size();
    int x = worker[0].x;
    for(int i = 0; i < size; i++) {
        if(x != worker[i].x) return false;
    }
    return true;
}

int solve(vector<Point>& f_worker, vector<Point>& s_worker) {
    vector<int> chosen;
    int ret = 0;
    for(int i = 0; i <= N*N-M; i++) {
        for(int j = 0; j < M; j++) {
            f_worker.push_back({(i+j)/N,(i+j)%N});
        }
        for(int j = i+M; j <= N*N-M; j++) {
            for(int k = 0; k < M; k++) {
                s_worker.push_back({(j+k)/N,(j+k)%N});
            }
            if(is_all_same_row(f_worker) and is_all_same_row(s_worker)) {
                int f = get_max(0,f_worker,chosen);
                int s = get_max(0,s_worker,chosen);
                ret = max(ret,f+s);
            }
            for(int k = 0; k < M; k++) {
                s_worker.pop_back();
            }
        }
        for(int j = 0; j < M; j++) {
            f_worker.pop_back();
        }
    }
    return ret;
}

void input() {
    cin >> N >> M >> C;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}

int main() {
    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        vector<Point> f_worker, s_worker;
        cout << '#' << t << ' ' << solve(f_worker,s_worker) << '\n';
    }
    return 0;
}

---

4. 주의할 점

• 벡터를 사용하고 벡터를 넘겨줄 때, 특별한 일이 없으면 참조의 형태로 넘겨주는 것이 좋다. 참조로 넘겨주지 않으면 새로운 벡터를 만들어서 복사하는 형태이기 때문에, 오버헤드가 발생해 소요 시간이 더 길어질 수 있다.