어흥
[SWEA 2115] 벌꿀채취 (C++) 본문
728x90
반응형
문제 링크: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
1. 주의할 점
- 두 일꾼이 같은 선택된 벌꿀통을 고르면 안된다
- 각 칸을 기준으로 최대 M칸까지 오른쪽으로 골랐을때의 최대 가중치를 저장한다
2. 구현
- Check[][] 배열을 false로 초기화시켜서 같은 벌꿀통을 고르지 않도록 확인하기 위해 false로 전부 초기화한다
- DFS() 사용하여 해당 칸을 골랐을 때 기준으로 최대값을 (가중치의 내림차순 순서로 정의)우선순위큐에 저장한다
- M개의 벌꿀통중에서 특정 벌꿀통을 고르거나 고르지 않는 경우를 고려하기 위해 DFS를 사용한다(백트레킹)
- DFS에선 if (x == max_x || x == num) 조건문을 통해 최대 범위를 벗어나지 않도록 설정한다
- DFS에서 받는 매개변수는 (현재 Y, 현재 X, 초기 X + M, 벌꿀의 총합, 가중치(제곱들의 합))
- 우선순위큐에서 1개씩 추출하면서 같은 벌꿀통에서 골랐을 경우 Continue, 아닐 경우 뽑은 후, Check[][]배열을 설정하여 같은 벌꿀통에서 고르지 않도록 설정한다
- 위의 과정을 2명의 일꾼이 골랐을 때까지 반복한다
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
struct info {
int r, c, val;
};
struct cmp {
bool operator()(info& a, info& b) {
return a.val < b.val;
}
};
info tmp;
int num, result, c, con, maxi;
int arr[10][10];
bool check[10][10];
priority_queue<info, vector<info>, cmp> pq;
void dfs(int y, int x, int max_x, int sum, int cal) {
if (x == max_x || x == num) { //최대 범위를 벗어난 경우
maxi = max(maxi, cal);
return;
}
if (arr[y][x] + sum <= c) //채취한 경우
dfs(y, x + 1, max_x, arr[y][x] + sum, cal + arr[y][x] * arr[y][x]);
dfs(y, x + 1, max_x, sum, cal); //채취 안한 경우
}
int main() {
int test;
cin >> test;
for (int t = 1; t <= test; t++) {
cin >> num >> con >> c;
for (int i = 0; i < num; i++)
for (int j = 0; j < num; j++) {
cin >> arr[i][j];
check[i][j] = false;
}
//초기화
while (!pq.empty())
pq.pop();
result = 0;
for (int i = 0; i < num; i++)
for (int j = 0; j <= num - con; j++) {
maxi = 0;
dfs(i, j, j + con, 0, 0);
tmp.c = j;
tmp.r = i;
tmp.val = maxi;
pq.push(tmp);
}
int remain = 0;
while (!pq.empty()) {
int cx = pq.top().c;
int cy = pq.top().r;
int cv = pq.top().val;
pq.pop();
bool avail = true;
for (int i = cx; i < min(cx + con, num); i++) {
if (check[cy][i]) {
avail = false;
break;
}
}
if (avail) {
result += cv;
remain++;
for (int i = cx; i < min(cx + con, num); i++)
check[cy][i] = true;
}
if (remain == 2) break;
}
cout << "#" << t << " " << result << '\n';
}
return 0;
}
728x90
반응형
'알고리즘 > SWEA' 카테고리의 다른 글
[SWEA 1949] 등산로 조성 (C++) (0) | 2021.04.16 |
---|---|
[SWEA 2477] 차량 정비소 (C++) (0) | 2020.08.30 |
[SWEA 1824 7258] 혁진이의 프로그램 검증 (C++) (0) | 2020.06.05 |
[SWEA 5650] 핀볼 게임 (C++) (2가지 풀이) (0) | 2020.05.31 |
[SWEA 1953] 탈주범 검거 (JAVA) (0) | 2020.05.28 |
Comments