ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2115.벌꿀채취
    알고리즘/SW Expert Academy 2020. 6. 23. 02:02

    이번에 풀어볼 문제는 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, 0sizeof(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

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

     

     


     

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

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

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

    반응형

    '알고리즘 > SW Expert Academy' 카테고리의 다른 글

    2477.차량 정비소  (2) 2020.07.07
    2105.디저트 카페  (0) 2020.06.27
    4008.숫자 만들기  (0) 2020.06.19
    5658.보물상자 비밀번호  (0) 2020.06.18
    1767.프로세서 연결하기  (0) 2020.06.16

    댓글

Designed by Tistory.