10*10 그리드를 주고 맨 왼쪽 위를 반드시 포함하는 rectangle 을 flip시킬 수 있을 때
최소 몇번만에 모든 그리드를 0으로 만들 수 있는지 물어보는 문제다.
그리드를 s[n][n]이라고 하자.
s[i][j] == 1이라면 이걸 flip시키려면
0,0 ~ k,l ( k>=i, l>=i ) 에서 flip시켜야 한다.
만약 n-1,n-1 번째가 1이라면 반드시 전체를 flip시켜야 한다는 뜻이다.
따라서 그리디하게 n-1,n-1부터 0,0까지 훑어보면서 s[i][j] == 1이라면 flip시킨다.
#include <iostream> using namespace std; int n, ans; char s[10][11]; void flip(int i,int j) { for (int k = 0; k <= i; ++k) for (int l = 0; l <= j; ++l) s[k][l] = s[k][l] == '1' ? '0' : '1'; } int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n; for (int i = 0; i < n; ++i) cin >> s[i]; for (int i = n - 1; i >= 0; --i) for (int j = n - 1; j >= 0; --j) { if (s[i][j] == '1') { ans++; flip(i, j); } } cout << ans << '\n'; return 0; } | cs |
'BOJ' 카테고리의 다른 글
| 11978 Mowing the Field (Bronze) (0) | 2018.11.10 |
|---|---|
| 11977 Angry Cows (Bronze) (0) | 2018.11.10 |
| 1909 냄새 싫어 (0) | 2018.11.07 |
| 5431 책 쌓기 (0) | 2018.11.07 |
| 16235 나무 재테크 (0) | 2018.10.22 |