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

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

작성

181

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)를 더하는 것이 행과 열의 연산을 모두 포함하는 것 같기도 한데 원리(?)에 대해 이해하기가 어렵습니다. 도와주세요!!

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 동글님 ㅎㅎ

행을 뒤집는 연산에 대한 +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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

동글

질문자

아 문제를 잘못 이해하고 있어서 연산의 개수도 최소화라고 이해했네요ㅜㅜ 이미 최적해라고 가정된 상태라서 sum에 더할 수 있었더군요!! 답변 감사합니다

인프런 커뮤니티 질문&답변

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