2115.벌꿀채취
이번에 풀어볼 문제는 SW Expert의 2115번 문제 벌꿀채취이다.
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
난이도는 쉬운 편인거 같은데 오히려 나의 문제점을 확실히 볼 수 있었다.
문제점은 바로 아직 재귀함수를 제대로 못다루는 것이다. 이 문제는 재귀로 풀 수 있을 것 같았는데
솔직히 재귀로 풀면 설계에 실수해서 시간안에 못 풀 것 같기도 했고 그냥 푸는게 실수도 적을 것 같으면서 더 쉬울 것 같았다....
=> 재귀로 다시 풀어 봐야겠다.
이 문제는 나처럼 그냥 시키는대로 풀어도된다. 코딩에 정답은 없다지만 코드의 효율이 좋지 않다는건 실감할 수 있었다.
그 이유 중 하나는 이 문제는 조합으로 풀어야하는 문제라는 걸 느꼈으나 나는 순열로 풀어서 불필요(?)한 연산을 진행하였다.
-> 이유는 우선 시간 복잡도가 순열로 풀어도 가능하다고 판단했고 조합을 사용할 때의 예외처리가 떠오르지 않았다.
분명 재귀함수를 이용해서도 풀 수 있다는 것도 직감할 수 있었지만 사용하지 못했다.
결론 : 꿀통의 숫자들의 조합이라던지 이런 부분들에 있어서 좋은 코드가 아닌 거 같다.
다른사람 코드를 보고 공부해야겠다...
이 문제는 처음봤을 때 느낀점은 그냥 Brute force?? 아니면 그냥 2가지(2번)의 조합을 구하면 되는 문제이다.
1. 하나는 꿀통 내에서의 최대값의 조합이다.
2. 나머지 하나는 두 번째 꿀통에서의 조합이다.
=> 첫 번째 꿀통이 기준이 되므로 첫 번째 꿀통에서의 조합은 크게 신경쓸 것 없이 한 칸씩 이동하면서 기준을 잡으면 된다.
=> 주의할 점은 연속된 M이 꿀통이기 때문에 줄바꿈 예외처리만 잘해주면된다.
< Code 설명 >
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
#pragma warning(disable:4996) #include <iostream>
#include <deque>
#include <algorithm>
#include <string.h>
using namespace std;
int T, N, M, C;
int map[10][10]; // 꿀 map
deque<int>honey1; // 꿀통 1
deque<int>honey2; // 꿀통 2
int honey_jo(deque<int>&honey){ // 꿀통 내부에서의 최대 조합
sort(honey.begin(), honey.end()); // 오름차순 정렬
int max = -987654321; // 최대값
int sum = 0; // 숫자들의 합이 저장되는 변수
int ans = 0; // 숫자 제곱들의 합이 저장되는 변수
do{
for (int i = 0; i < honey.size(); i++){ //꿀통의 크기만큼 반복
if (sum + honey[i] <= C){ // 최대 수집할 수 있는 꿀양보다 작아야함
ans += honey[i] * honey[i]; //꿀의 값 제곱만큼 더해줌
sum += honey[i]; // 숫자들의 합을 누산해서 최대 수집양과 비교함
}
}
if (max < ans) // 최대값 저장
max = ans;
ans = 0; // 숫자 제곱들의 합 초기화
sum = 0; // 숫자들의 합 초기화
} while (next_permutation(honey.begin(),honey.end())); // 순열 확인
while (!honey.empty()) // 꿀통 초기화
honey.pop_back();
return max; // 최대값 리턴
}
void init(){ // 초기화
memset(map, 0, sizeof(map));
}
int main() {
freopen("2115.txt", "r", stdin);
cin >> T;
for (int z = 1; z <= T; z++){
cin >> N >> M >> C;
init(); //초기화
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
cin >> map[i][j]; // 벌꿀 map 저장
}
}
int max_value = -987654321; // 최대값 저장
int box1 = 0; // 꿀통 1에서의 최대값 변수
int box2 = 0; // 꿀통 2에서의 최대값 변수
for (int i = 0; i < N; i++){
for (int j = 0; j < N; j++){
if (j + M - 1 < N){ // x좌표에 꿀통의 크기만큼 더한거 -1이 N의 범위안에 존재하면
for (int w = 0; w < M; w++) // 꿀통의 크기만큼 저장
honey1.push_back(map[i][j + w]); // 꿀통 1에서 사용되는 꿀들을 저장
box1 = max(box1, honey_jo(honey1)); // 꿀통 1에서 조합을 통해 나올 수 있는 최대값 box1에 저장
if (i == N - 1 && j >= N - M -1) // 기준점이 되는 꿀통1이 너무 커져서 꿀통 2가 올자리가 없는 경우
continue; // pass
// box2 일때
int v = i; // 해당 y좌표 저장
int k = j+M;// 꿀통 2의 첫번째 좌표는 꿀통 1의 x보다 + M 이므로
while (true){
if (v >= N) // 꿀통 2가 y좌표가 N의 범위를 초과하는 경우
break; // 탐색 중지
if (k + 1 < N){ //꿀통 2의 x좌표가 N 범위 내에 존재하는 경우
for (int w = 0; w < M; w++)
honey2.push_back(map[v][k + w]); // 해당 꿀들을 꿀통 2에 저장
box2 = max(box2, honey_jo(honey2)); // 꿀통 2에서 만들 수 있는 최대 값 저장
k += 1; // 꿀통 2의 x좌표 +1
if (k + M > N){ // 꿀통 2의 마지막칸의 x좌표가 N의 범위를 벗어난 경우
v += 1; // y축 +1
k = 0; // x축은 0부터
}
}
else if (k + 1 >= N){ // 꿀통 2의 두 번째 칸 이상의 x좌표가 N의 범위를 벗어나는 경우
v += 1; // y축 +1
k = 0; // x축은 0부터
}
}
// 최대값 구하기
if (max_value < box1 + box2) // 두 꿀통의 최대값을 더한 것들 중의 최대값 저장
max_value = box1 + box2;
box1 = 0; // 꿀통 1의 최대값 초기화
box2 = 0; // 꿀통 2의 최대값 초기화
}
}
}
cout << "#" << z << " " << max_value << "\n";
}
return 0;
}
|
cs |
# 보강해야할 점 : 재귀함수, 조합, 순열 => 결국 같은 맥락으로 이용할 수 있는 것들이네....;;
재귀함수 풀이는 이분의 블로그가 가장 깔끔한거 같다.
=> 재귀로 풀면 코드는 깔끔해지나 생각보다 풀기 까다로웠다. 부족하다는 증거...