https://www.acmicpc.net/problem/1285
1285번: 동전 뒤집기
첫째 줄에 20이하의 자연수 N이 주어진다. 둘째 줄부터 N줄에 걸쳐 N개씩 동전들의 초기 상태가 주어진다. 각 줄에는 한 행에 놓인 N개의 동전의 상태가 왼쪽부터 차례대로 주어지는데, 앞면이 위
www.acmicpc.net
임의의 한 행, 한 열에 놓은 N개의 동전을 뒤집는다.
동전을 적절히 뒤집어 T의 최소 개수 구하기
각 동전은 행 또는 열을 바꿀 때, 그 결과가 바뀔 수 있다. 즉, 모든 동전은 2번의 변환이 가능하다.
따라서 접근 방식은 다음과 같다. 3x3 크기의 행렬로 동전이 있다고 가정하자.
그러면, 행을 바꾸는 경우는 아래와 같이 총 7가지가 있다.
① 모든 행을 바꾸지 않는 1가지
② 모든 행을 다 바꾸는 1가지
③ 2개의 행을 골라 바꾸는 3가지
④ 1개의 행을 골라 바꾸는 3가지
하나의 열의 동전의 총 개수는 N개로 동일하기 때문에 뒤집은 경우와 뒤집지 않은 경우 중
더 적은 경우로 계산을 하면 됨.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <iostream>
#include <string>
#include <vector>
using namespace std;
char flip(char x)
{
if (x == 'H') return 'T';
else return 'H';
}
int main()
{
int n;
cin >> n;
vector<string> a(n);
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
int ans = n * n;
//state는 행을 바꿀지 말지를 의미
//모든 경우의 수 표현을 위해 비트마스크
for (int state = 0; state < (1 << n); state++)
{
int sum = 0;
// j는 열
for (int j = 0; j < n; j++)
{
int cnt = 0;
// i는 행
for (int i = 0; i < n; i++)
{
char cur = a[i][j];
// 비트마스크를 통해 뒤집는지 안 뒤집는지 결정
if (state & (1 << i))
cur = flip(cur);
if (cur == 'T')
cnt += 1;
}
// 열은 뒤집을 필요가 없다.
// 개수가 적은 걸 고르면 그걸 뒤집은 걸로 생각하면 끝
sum += min(cnt, n - cnt);
}
if (ans > sum) ans = sum;
}
cout << ans << '\n';
return 0;
}
|
cs |
