24.02.26 22:55 작성
·
166
0
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)를 더하는 것이 행과 열의 연산을 모두 포함하는 것 같기도 한데 원리(?)에 대해 이해하기가 어렵습니다. 도와주세요!!
답변 1
0
2024. 02. 27. 08:31
안녕하세요 동글님 ㅎㅎ
행을 뒤집는 연산에 대한 +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점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
2024. 02. 28. 00:41
아 문제를 잘못 이해하고 있어서 연산의 개수도 최소화라고 이해했네요ㅜㅜ 이미 최적해라고 가정된 상태라서 sum에 더할 수 있었더군요!! 답변 감사합니다