[프로그래머스] 2차원 동전 뒤집기 - C++

한수는 직사각형 모양의 공간에 놓인 동전들을 뒤집는 놀이를 하고 있습니다. 모든 동전들은 앞과 뒤가 구분되어 있으며, 동전을 뒤집기 위해서는 같은 줄에 있는 모든 동전을 뒤집어야 합니다. 동전들의 초기 상태와 목표 상태가 주어졌을 때, 초기 상태에서 최소 몇 번의 동전을 뒤집어야 목표 상태가 되는지 알아봅시다.

예를 들어, 위 그림에서 맨 왼쪽이 초기 상태, 맨 오른쪽이 목표 상태인 경우에 대해 알아봅시다. 그림에서 검은색 원은 앞면인 동전, 흰색 원은 뒷면인 동전을 의미합니다. 초기 상태에서 2행과 4행의 돌들을 뒤집으면, 두 번째 그림이 됩니다. 그 후, 2열, 4열, 5열의 돌들을 순서대로 뒤집는 다면, 총 5번의 동전 뒤집기를 통해 목표 상태가 되며, 이 경우가 최소인 경우입니다.

직사각형 모양의 공간에 놓인 동전들의 초기 상태를 나타내는 2차원 정수 배열 beginning, 목표 상태를 나타내는 target이 주어졌을 때, 초기 상태에서 목표 상태로 만들기 위해 필요한 동전 뒤집기 횟수의 최솟값을 return 하는 solution 함수를 완성하세요. 단, 목표 상태를 만들지 못하는 경우에는 -1을 return 합니다.

---

행과 열을 뒤집는 순서는 상관 없지만

01110

10001

10001

10001

10001

과 같이 1행 1열 5열 을 뒤집는 것이 가장 적게 걸리는 경우의 수는 일반적인 규칙으로는 찾을 수 없다.

따라서 조합을 이용하여 뒤집을 행을 결정하고 뒤집은 뒤 열이 같은 숫자로 이루어져 있으면 가능한 경우이다. 

---

처음에는 행 과 열을 각각 보면서 첫쨰자리가 1이라면 뒤집는 방법을 사용했는데 반례가 도저히 떠오르지 않았다. 그래서 검색을 했더니 이와 같은 방식으로 푼 사람이 없었다. 그래서 생각을 하다 보니 위와 같은 반례가 떠올랐고 규칙 없이 일단 뒤집어 봐야 한다는 것을 알게 되었다. 그럼에도 똑같은 예제가 틀렸는데 이는 정사각형이 아니라 직사각형이었기 때문이었다.. 문제를 다시 보니 "한수는 직사각형 모양의 공간"이라고 되어있었다. 문제를 진짜 여러 번 다시 읽었는데 못 읽어 냈다. 참 아쉽다!