2115.벌꿀채취

이번에 풀어볼 문제는 SW Expert의 2115번 문제 벌꿀채취이다.

SW Expert Academy

난이도는 쉬운 편인거 같은데 오히려 나의 문제점을 확실히 볼 수 있었다.

문제점은 바로 아직 재귀함수를 제대로 못다루는 것이다. 이 문제는 재귀로 풀 수 있을 것 같았는데

솔직히 재귀로 풀면 설계에 실수해서 시간안에 못 풀 것 같기도 했고 그냥 푸는게 실수도 적을 것 같으면서 더 쉬울 것 같았다....

=> 재귀로 다시 풀어 봐야겠다.

 

이 문제는 나처럼 그냥 시키는대로 풀어도된다.  코딩에 정답은 없다지만 코드의 효율이 좋지 않다는건 실감할 수 있었다.

그 이유 중 하나는 이 문제는 조합으로 풀어야하는 문제라는 걸 느꼈으나 나는 순열로 풀어서 불필요(?)한 연산을 진행하였다.

-> 이유는 우선 시간 복잡도가 순열로 풀어도 가능하다고 판단했고 조합을 사용할 때의 예외처리가 떠오르지 않았다.

 

 

분명 재귀함수를 이용해서도 풀 수 있다는 것도 직감할 수 있었지만 사용하지 못했다.

결론 : 꿀통의 숫자들의 조합이라던지 이런 부분들에 있어서 좋은 코드가 아닌 거 같다.

다른사람 코드를 보고 공부해야겠다...

 

---

 

이 문제는 처음봤을 때 느낀점은 그냥 Brute force?? 아니면 그냥 2가지(2번)의 조합을 구하면 되는 문제이다.

1. 하나는 꿀통 내에서의 최대값의 조합이다.

2. 나머지 하나는 두 번째 꿀통에서의 조합이다.

  => 첫 번째 꿀통이 기준이 되므로 첫 번째 꿀통에서의 조합은 크게 신경쓸 것 없이 한 칸씩 이동하면서 기준을 잡으면 된다.

  => 주의할 점은 연속된 M이 꿀통이기 때문에 줄바꿈 예외처리만 잘해주면된다.

 

---

 

< Code 설명 >

#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;
}

# 보강해야할 점 : 재귀함수, 조합, 순열 => 결국 같은 맥락으로 이용할 수 있는 것들이네....;;

 

 

---

 

재귀함수 풀이는 이분의 블로그가 가장 깔끔한거 같다.

=> 재귀로 풀면 코드는 깔끔해지나 생각보다 풀기 까다로웠다. 부족하다는 증거...

* 참고 : https://charm-charm.postype.com/post/3534726