ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 2112.보호필름
    알고리즘/SW Expert Academy 2020. 7. 30. 01:09

    이번에 풀어볼 문제는 SW Expert 2112번 보호 필름이다. 

    거의다 풀었는데 재귀함수 호출 부분에서 실수가 있었다.. 젠장..

    블로그를 뒤져보던 중 운 좋게 가장 비슷한 풀이를 찾았고 참조하였다.

    아무것도 넣지않고 테스트하는 것을 재귀에 포함시켜서 진행했어야 했는데

    이 부분을 재귀에서 빼고 진행했더니 경우의 수를 제대로 구하지 못했다...

    코드 1줄을 추가 했을 뿐인데 정답이 맞았다.. 크흠....

    참고 : https://jongnan.tistory.com/entry/SW-Expert-2112-%EB%B3%B4%ED%98%B8-%ED%95%84%EB%A6%84

     

    SW Expert Academy

    SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!

    swexpertacademy.com

    이 문제를 해결하기 위해서는 크게 2가지를 구현하면된다.

     

    1. 약물 투여

    2. 통과 테스트

     

    약물 투여의 경우 최소 2번을 진행해야하고 투여없이 테스트를 통과한다면 0을 출력하고

    그게 아니라면 최소 2번 이상의 투여 후 통과할 수 있는 최소 투여 횟수를 출력하면 된다.

     

    약물투여를 구현함에 있어서 재귀함수를 사용했고 통과테스트는 그저 구현하면 된다.

    약물을 투여하기 위해서는 A를 넣을지 B를 넣을지와 투여 전에 해당 가로라인을 미리 저장해주어야 한다는 점이 Point이다.

     


     

    < 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
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113

    #pragma
     warning(disable:4996)
    #include <iostream>
    #include <string.h>
    #include <algorithm>
    #define X 14
    #define Y 21
     
    using namespace std;
     
    int T, D, W, K;
     
    int map[X][Y];
    int ans; // 정답
     
    void init(){ // 초기화
        memset(map, 0sizeof(map));
        ans = 987654321;
    }
     
    bool test(){
        int start; // 기준이 되는 숫자 변수
        int cnt;   // 연속된 숫자의 개수가 저장되는 변수
        int pass = 0// 테스트에 통과한 세로줄 개수가 저장되는 변수
     
        for (int i = 0; i < W; i++){
            start = map[0][i]; // 기준 숫자는 세로줄 제일 첫 번쨰 값
            cnt = 1;           // 시작 숫자가 존재하므로 1로 시작
            for (int j = 1; j < D; j++){
                if (map[j][i] == start) //연속되고 있는 숫자와 다음수가 같은 경우
                    cnt += 1;           // 연속된 수의 갯수 +1
     
                else if (map[j][i] != start){ // 연속되고 있는 숫자와 다음 수가 다른경우
                    start = map[j][i];        // 달라진 수를 기준으로 바꿔준다.
                    cnt = 1;                  // 달라진 수로 시작되었으므로 1로 초기화
                }
     
                if (cnt == K){ // 연속된 수가 K개면 해당 세로줄 검사 통과
                    pass += 1// 통과된 세로줄 수 +1
                    break;     // 바로 다음탐색으로 넘어감
                }
     
            }
            if (cnt < K)  // 탐색이 모두 끝날 때 까지 연속된 숫자가 K보다 작으면 테스트 실패이므로
                return false// false 반환
        }
        if (pass == W) // 테스트를 통과한 세로줄의 수와 세로줄의 갯수가 같으면 통과이므로 true 반환 
            return true;
    }
     
    void copy_and_repair(int *tmp, int idx, bool mode){ // 복사 또는 복구
     
        if (!mode){ // copy
            for (int i = 0; i < W; i++)
                tmp[i] = map[idx][i];
        }
     
        else{      // repair
            for (int i = 0; i < W; i++)
                map[idx][i] = tmp[i];
        }
     
    }
     
    void change_film(int idx, int alpa){ // 투약
        for (int i = 0; i < W; i++)
            map[idx][i] = alpa;
    }
     
    void search(int idx, int cnt){
     
     
        if (ans <= cnt) // 정답보다 cnt가 크면 굳이 할 필요가 없으므로 
            return;    // 반환
     
        if (idx >= D){ // idx가 세로길이를 넘어버리면
            if (test())   // 테스트 진행
                ans = min(ans, cnt); // 테스트에 통과하면 해당 최소 시약 값과 정답변수 중 최소값을 저장
            return;
        }
     
        search(idx + 1, cnt); // 투약없이 진행
     
     
        int tmp[Y]; // 임시 저장 변수
        copy_and_repair(tmp, idx, 0); // 약물을 투여할 가로 라인 임시 저장
        change_film(idx, 0); // 해당 가로라인 A로 칠함
        search(idx + 1, cnt + 1); // 약물 투여한 상태로 다시 탐색
        copy_and_repair(tmp, idx, 1); // 약물 투여한 라인 복구
     
        copy_and_repair(tmp, idx, 0); // 약물을 투여할 가로 라인 임시 저장
        change_film(idx, 1); // 해당 가로라인 B로 칠함
        search(idx + 1, cnt + 1); // 약물을 투여한 상태로 다시 탐색 
        copy_and_repair(tmp, idx, 1); // 약물 투여한 라인 복구
     
    }
     
    int main() {
        freopen("2112.txt""r", stdin);
        cin >> T;
        for (int z = 1; z <= T; z++){
            init();
            cin >> D >> W >> K;
     
            for (int i = 0; i < D; i++){
                for (int j = 0; j < W; j++){
                    cin >> map[i][j];
                }
            }
            search(00);   
            cout << "#" << z << " " << ans << "\n";
        }
        return 0;
    }
    cs

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

    4012.요리사  (0) 2020.08.06
    2112.보호필름  (0) 2020.07.30
    1953.탈주범 검거  (0) 2020.07.28
    1952.수영장  (0) 2020.07.23
    2382.미생물격리  (0) 2020.07.21
    2383.점심 식사시간  (0) 2020.07.10

    댓글 0

Designed by Tistory.