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

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

---

1. 이해하기

• 보호 필름의 셀들은 각 특성을 갖는다.
• 단면의 모든 세로방향에 대해서 동일한 특성의 셀들이 K개 이상 연속적으로 있는 경우에만 성능검사를 통과하게 된다.
• 성능 검사에 통과하기 위해서 약품을 사용한다.
  • 약품은 막 별로 투입할 수 있으며 이 경우 투입하는 막의 모든 셀들은 하나의 특성으로 변경된다.
• 약품 투입 횟수를 최소로 하여 성능검사를 통과할 수 있는 방법을 찾는 문제.

---

2. 구현하기

• 보호 필름이 성능검사를 통과했는지 알아본다.

  bool is_passed() {
      for(int i = 0; i < W; i++) {
          bool flag = false;
          int cnt = 1;
          for(int j = 0; j < D-1; j++) {
              if(film[j][i] == film[j+1][i]) cnt++;
              else {
                  cnt = 1;
              }
              if(cnt == K) {flag = true; break;}
          }
          if(!flag) return false;
      }
      return true;
  }

• 각 단면마다 약품을 넣어보고 검사를 통과하는 지 본다. 이 때, 약품 투입의 최솟값을 찾는다.

  • 각 약품을 넣어보기 전에 현재 값과 다음 값을 비교한다음 다음 값이 더 작을 경우에만 실행한다. 실행시간을 많이 낮춰준다.

  void insert_chemical(int row, int che) {
      for(int i = 0; i < W; i++) {
          film[row][i] = che;
      }
  }
  
  int solve(int row, int cnt) {
      if(row == D) {
          if(is_passed()) return cnt;
          else return K;
      }
  
      for(int i = 0; i < W; i++) {
          temp[row][i] = film[row][i];
      }
  
      int ret = MAX;
      ret = min(ret,solve(row+1,cnt));
      insert_chemical(row,0);
      if(cnt+1 < ret) ret = min(ret,solve(row+1,cnt+1));
      insert_chemical(row,1);
      if(cnt+1 < ret) ret = min(ret,solve(row+1,cnt+1));
  
      for(int i = 0; i < W; i++) {
          film[row][i] = temp[row][i];
      }
      return ret;
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
const int MAX = 987654321;
int film[13][20];
int temp[13][20];
int D,W,K;

bool is_passed() {
    for(int i = 0; i < W; i++) {
        bool flag = false;
        int cnt = 1;
        for(int j = 0; j < D-1; j++) {
            if(film[j][i] == film[j+1][i]) cnt++;
            else {
                cnt = 1;
            }
            if(cnt == K) {flag = true; break;}
        }
        if(!flag) return false;
    }
    return true;
}

void insert_chemical(int row, int che) {
    for(int i = 0; i < W; i++) {
        film[row][i] = che;
    }
}

int solve(int row, int cnt) {
    if(row == D) {
        if(is_passed()) return cnt;
        else return K;
    }

    for(int i = 0; i < W; i++) {
        temp[row][i] = film[row][i];
    }

    int ret = MAX;
    ret = min(ret,solve(row+1,cnt));
    insert_chemical(row,0);
    if(cnt+1 < ret) ret = min(ret,solve(row+1,cnt+1));
    insert_chemical(row,1);
    if(cnt+1 < ret) ret = min(ret,solve(row+1,cnt+1));

    for(int i = 0; i < W; i++) {
        film[row][i] = temp[row][i];
    }
    return ret;
}

void input() {
    cin >> D >> W >> K;
    for(int i = 0; i < D; i++) {
        for(int j = 0; j < W; j++) {
            cin >> film[i][j];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int T;
    cin >> T;
    for(int t = 1; t <= T; t++) {
        input();
        cout << '#' << t << ' ' << solve(0,0) << '\n';
    }
    return 0;
}