동전 뒤집기

---

이문제 일단 DFS로 풀려다가 뭔가 이상했음.

1행을 뒤집고 1열을 뒤집고 다시 1행을 뒤집는 경우의 수가 존재함.

DFS는 아닌거같았음.

어려운 문제를 풀 때는 내가 생각한 로직이 맞지 않다.

=> 시간복잡도를 어떻게든 줄여야한다.

---

이 문제는 행만 뒤집으면된다.

n = 20일 경우 행을 뒤집고 안뒤집고 2^20 이라는 시간복잡도가 나온다.

행열 둘다 뒤집는 경우는 2^40 이라 못푼다.

행만 뒤집으면 열의 최적해는 정해져 있다.

코드 분석

for (int i = 1; i <= n; ++i)
{
	cin >> s;
	int value = i;
	for (int j = 0; j < s.size(); ++j)
	{
		if (s[j] == 'T') arr[i] |= value;
		value *= 2;
	}
}

이거 뭐임?

숫자 하나로 HTT, THT 이렇게 비트 마스킹으로 표현이 가능하다.

T가 켜져있는거라고 하면은 HHT는 4이고 HTT는 6이고, TTT는 7이다.

이런식으로 값을 가질 수 있도록 한 것이다.

---

~a

int a = 4;
a = ~a;

하는 경우

~a 는
100 -> 011 로 된다 
근데 사실은
1111 1111 1011 이런식으로 뒤집히는거임

값을 출력하면 -5가 나옴.

그래서 ~a = -(a + 1)과 같다.

음수를 표현하는 것은 2의 보수법으로 표현이 가능한데

1011 이라는 수(11)를 반전시킨 후

-> 0100 이렇게 반전된 수에 +1을 해주면

-> 0101이 된다. => -11

이게 1011의 음수표현방법이다.

~a 이해 ❗❗❗

~a = -(a + 1)과 같다. 이게 지금

이게 4인데 반전 시키면

-5가 된다.

그래서 ~a = -(a+1)

4를 반전한거는 == ~a

-(a + 1) 과 같다.
-(4 + 1) 과 같다.