4-B 정답코드에 대해 잘 이해가 안 됩니다.

Question

https://www.acmicpc.net/source/share/c19e6a890efe4edcb2a98fedca33b37b 안녕하세요. 4-b가 어려워 강의를 들었는데도 답지코드도 이해가 안되는 부분이 있어서 질문드립니다.   16번째 라인에 sum += min(cnt, n - cnt); 해당 부분이 이해가 잘 안 됩니다.   cnt를 구하는 부분이나 n-cnt를 하는 부분은 열을 뒤집을지 말지를 결정하기 위해 필요한 값이라는 것은 알고 있습니다. 하지만 min(cnt, n-cnt)를 구하여 열을 뒤집을지말지를 결정해서 연산+1 을 하는 것이 아니라, 더한다는 의미가 어떤 것인지 잘 이해가 안 갑니다. 또한 행을 뒤집으면 최적해가 이미 정해졌다는 것까지는 강의를 듣고 어렴풋이 알 것 같은데, 행을 뒤집는 연산에 대한 +1은 하지 않는지도 궁금합니다 . (행을 두개 뒤집는다든지, 한 개 뒤집는다든지,, 등)   min(cnt, n-cnt)를 더하는 것이 행과 열의 연산을 모두 포함하는 것 같기도 한데 원리(?)에 대해 이해하기가 어렵습니다. 도와주세요!!

큰돌 · Answer

안녕하세요 동글님 ㅎㅎ 행을 뒤집는 연산에 대한 +1은 하지 않는지도 궁금합니다 . >> 애초에 그 연산에 대한 + 1은 중요하지 않습니다. 문제를 잠시 볼까요? 첫째 줄에 한 행 또는 한 열에 놓인 N개의 동전을 모두 뒤집는 작업들을 수행하여 뒷면이 위를 향하여 놓일 수 있는 동전의 최소 개수를 출력한다. 어떻게든 최소화 시키는게 이 문제의 핵심이죠? min(cnt, n-cnt)를 더하는 것이 행과 열의 연산을 모두 포함하는 것 같기도 한데 원리(?)에 대해 이해하기 >> 자 우리가 마지막 기저사례까지 왔다고 칠게요. void go(int here){ if(here == n + 1){ int sum = 0; for(int i = 1; i <= (1 << (n - 1)); i *= 2){ int cnt = 0; for(int j = 1; j <= n; j++) if(a[j] & i)cnt++; sum += min(cnt, n - cnt); } here == n + 1인 상태입니다. 동전이 뒤집어진 것을 보니까. ooooxxxooo 이렇게 뒤집어져있어요. o가 뒷면이죠. 뒷면 : 7개 / 앞면 3개 이상태에서 이 행 자체를 한번 더 뒤집어서 뒷면 : 3개 / 앞면 7개 를 만들어 뒷면을 최소화해서 3개로 만드는게 최적해지 않을까요? 그부분이 담긴 코드가 바로. sum += min(cnt, n - cnt); 입니다. 또 질문 있으시면 언제든지 질문 부탁드립니다. 좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :) 감사합니다. 강사 큰돌 올림.