260307

• 최근 풀이
  :

1) 타겟 위치가 다르다면 일단 뒤집는 것이 문제에서 찾고자 하는 답에 접근하는 최고의 방법이다.
-> 문제에서는 0과 1이 주어지기 때문에 다르면 뒤집어야지

2) 만약에 i,j를 다르면 우로 2칸, 아래로 2칸에 해당하는 3X3 부분집합을 뒤집어야 하고,

3) 그 다음에 해당하는 i,j + 1 이 다르다면 2번과 마찬가지 방법으로 뒤집자. 그런데 이렇게 하더라도 , 그 전 위치한 i,j에는 영향을 주지 않으므로, 그리디 알고리즘이라 생각함.

3) 마찬가지로 for문 2번으로 진행하다보면, 절대로 이전 위치 인덱스 해당하는 값들에 영향을 주지 않는다.
=> 확신에 들었다!!

---

그리디는 2개로 나뉘어 지는데

1. 탐욕
2. 최적부분이다.

• 나는 항상 탐욕 분류에 속한 문제만 풀어와서 어렵게 느껴짐.

최적부분 그리디

• 가장 작은 단위에서의 최적의 해를 구하면서
  이 해들이 모여서 전체 문제의 최적 해인지를 확인하는 과정.

해결 전략

• 문제
  : 2500 개의 칸에서 특정 칸을 뒤집고 안 뒤집고로 진행을 하면서
  b 행렬과 맞추는 문제이다.

// 한번에 뒤집을 때 9개를 뒤집는 거고
-> 모든 영역이라고 생각한다면 뒤집고 안뒤집고 이므로

• -> 2의 2500승이라고 할 수 있따.

• 브루트로는 못한다.

생각하기

• 브루트포스도 안되고, 이분탐색도 아니고, 그래프도 아니고, dp인가? 그리디인가? 생각된다.

• 이럴때는 그리디를 생각해봐야 하고, 지금은 탐욕이 아닌
  -> 가장 작은 단위부터 생각을 해보자.
  

핵심.

• 하나의 포지션을 기준으로 해서 b행렬과 동일한지를 확인하면
  뒤집을지 안뒤집을지를 결정할 수 있다.