[SWEA] 2112. [모의 SW 역량테스트] 보호 필름

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu

SW Expert Academy

모든 막(가로 방향)에 약품을 넣지 않는 경우/ A약품을 투입하는 경우/ B약품을 투입하는 경우를 구해주면 된다.

이미 합격기준을 통과한 최소 개수가 있는 경우, 해당 최소 개수보다 더 큰 경우는 탐색하지 않는다. 즉 약품을 더 투입하는 경우를 구하지 않으면서 탐색 시간을 줄일 수 있다.

 

성능 검사를 할 때는 모든 세로를 검사해주면 되는데

k개만큼의 연속된 같은 셀이 존재한다면 해당 열은 통과이고 이렇게 모든 열이 통과해야 한다.

 

나는 밑의 코드에서 bool변수 두 개를 적당히 활용하여 구현하였다.

먼저 flag 하나를 처음에 true로 두고 연속된 k개가 같지 않다면 false로 바꾸고 한 칸 내려와서 다시 k개만큼을 비교한다.

만약에 k개만큼 같았다면(합격 기준을 통과했다면) flag가 그대로 true인 상태이므로 해당 열은 통과이고 다음 열 검사로 넘어간다.

 

그리고 각 열이 통과했는지 확인해줄 bool 변수 colok를 처음에 false로 두고, 위에서 flag가 true가 됐을 때 같이 true가 되도록 해줬다.

해당 열의 검사가 끝났는데 colok가 false라면 해당 열은 통과를 하지 못했으므로 전체 검사도 통과하지 못하므로 바로 false를 리턴한다.

사실 변수 하나만 써도 적당히 잘 구현할 수 있긴 하다.

 

그리고 이 문제에서 실수할 수 있는 부분은 k가 1인 경우이다.

k가 1인 경우는 합격기준이 1이기 때문에 1개만 연속적으로 같으면 되므로 무조건 합격기준을 통과한다.

이 경우에는 바로 0을 출력해주고 다음 테스트 케이스로 넘어간다.

#include <iostream>
#include <cstring>
using namespace std;
 
int ans;
int d, w, k;
 
 
bool check(int film[13][20]) {
    
    //모든 세로를 검사
    for (int j = 0; j < w; j++) {
        
        //j번열에 연속된 k개의 같은 셀이 있는지 검사
        bool colok = false;
        for (int i = 0; i <= d - k; i++) {
            
            bool flag = true;
            for (int l = i+1; l < i + k; l++) {
                if (film[i][j] != film[l][j]) {
                    flag = false;
                    break;
                }
            }
 
            //한번이라도 연속되는 k개의 같은 셀이 있다면 현재 열은 통과이다
            if (flag) {
                colok = true;
                break;
            }
        }
 
        //열이 하나라도 통과를 하지 못하면 바로 false를 리턴
        if (!colok) {
            return false;
        }
    }
 
    //위에서 false를 리턴하지 않았다면 검사를 통과한 것이다
    return true;
}
 
void mapcopy(int film[13][20], int newfilm[13][20]) {
    for (int i = 0; i < d; i++) {
        for (int j = 0; j < w; j++) {
            newfilm[i][j] = film[i][j];
        }
    }
}
 
void solve(int cnt, int index, int film[13][20]) {
    //현재 사용한 개수가 이미 최솟값(정답)보다 같거나 크다면 더 검사하지 않는다.
    if (cnt >= ans) return;
    //현재 상태에서 성능을 검사한다
    if (check(film)) {
        //성능 검사를 통과했다면 ans에 cnt를 저장
        ans = cnt;
        return;
    }
    //모든 막에 약품을 투입하는 경우를 구해줬다.
    if (index == d) return;
 
    int newfilm[13][20];
    mapcopy(film, newfilm);
 
 
    //index번째 막에 약품을 투입하지 않는다.
    solve(cnt, index + 1, newfilm);
 
 
    //index번째 막에 A약품을 투입한다.
    for (int j = 0; j < w; j++) {
        newfilm[index][j] = 0;
    }
    solve(cnt + 1, index + 1, newfilm);
 
 
    //index번째 막에 B약품을 투입한다.
    for (int j = 0; j < w; j++) {
        newfilm[index][j] = 1;
    }
    solve(cnt + 1, index + 1, newfilm);
 
}
 
 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int T;
    cin >> T;
    for (int tc = 1; tc <= T; tc++) {
        ans = 20;
        cin >> d >> w >> k;
 
        int film[13][20];
        for (int i = 0; i < d; i++) {
            for (int j = 0; j < w; j++) {
                cin >> film[i][j];
            }
        }
 
        //합격기준이 1인 경우에는 무조건 통과이므로 다음 테스트 케이스로 넘어간다
        if (k == 1) {
            cout << '#' << tc << ' ' << 0 << '\n';
            continue;
        }
        
        solve(0,0, film);
        cout << '#' << tc << ' ' << ans << '\n';
    
        
    }
 
 
 
    return 0;
}