[뒤집기] 1455번, 최소 뒤집기 구하기(1)

1. 문제 요약

/*
  문제 : 동전이 모두 앞면(0)이 나오도록 뒤집어라
  조건
    - 한 번 (a, b)를 뒤집으면 (0,0) ~ (a,b) 영역 모두 뒤집힌다
    - 뒤집은 횟수는 선택된 (a,b)수와 같다.
  출력 : 뒤집은 횟수를 구해라.
*/

 

2. 풀이

    /*
      * 풀이 과정
      
      * "제일 외곽부터 처리" : (우선순쉬1) row가 클수록 -> (우선순쉬2) col이 클수록
      
      * 예시
        00    11    00    10    00
        01 -> 10 -> 10  ->00  ->00
        
      * 직렬화시 : 0001 1110 0010 1000 0000
    */

풀이 개념 > 코드로 표현

(1) 맨 끝에서 부터 처리

한 번 뒤집을 때 (a, b) 지점까지 다 뒤집히므로, 제일 바깥쪽 영역부터 순회하면서 (0, 0)을 시행합니다.

case1. 기본 처리 

(2) 다음 순회 지점 우선 순위 : 같은 열이면 큰 행 자리

같은 열 순회가 끝나면 왼쪽 열으로 이동합니다.

case2. 15->14->13->12->11 ... 순서로 순회합니다.

(3) 순회방식은 논의 끝 -> Then, 1을 발견한다면?

현재 지점보다 큰 좌표는(더 이상 처리 대상이 아니므로), "읽어서 뒤집기 않기 위해(dont read)" 값을 2로 변환했습니다.

case3. 더 이상 뒤집지 않는 좌표 처리

해당 처리 코드.

 

3. 자화자찬

• 순회를 위해 삭제 연산을 값 변환으로 돌린 점

 

4. 코드

https://github.com/ukiKwon/algorithm-study/blob/master/%EB%92%A4%EC%A7%91%EA%B8%B0/1455.cpp