2112.보호필름

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

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

 

1. 약물 투여

2. 통과 테스트

 

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

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

 

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

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

 

---

 

< Code 설명 >

 

#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, 0, sizeof(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(0, 0);   
        cout << "#" << z << " " << ans << "\n";
    }
    return 0;
}