ohmy.codes

IP 61.73.0.0 Created 10-27 09:10
1
import java.util.*;
2
import java.util.stream.*;
3
import java.io.*;
4
5
6
public class Main {
7
// 모든 염기서열을 커버 가능한 최소 갯수
8
// 그게 존재 하냐?
9
// 최대 15개가 주어지기 때문에 최대 15개이다
10
11
// 공존할 수 있는 쌍을 찾기?
12
// 누구랑 공존할 지도 중요해
13
// 그 모든 경우의 쌍을 구해도 2^15이 안 됨 적은 갯수다.
14
// 모든 부분 집합을 살펴보자.
15
// 15면 14 제곱?
16
17
private static int N, M;
18
private static int cnt = 0;
19
private static List<String> DNAs;
20
21
private static List<Integer> subsets = new ArrayList<>();
22
private static Map<Integer, String> superDNAs = new HashMap<>();
23
24
25
static int answer;
26
// 이미 해본 조합을 또 하고 있는게 문제야.
27
// 줄일만큼 줄임. 반대 수가 있으면 바로 끝내기?
28
// 그래도 안 됨. 되는 조합을 저장하기?
29
static Map<Integer, Integer> combinations = new HashMap<>();
30
static void dfs(Integer set, int index, int cnt) {
31
if (cnt >= answer) {
32
return;
33
}
34
35
if (set == ((1 << N) - 1)) {
36
answer = cnt;
37
return;
38
}
39
40
int negative = (1 << N) - 1 - set;
41
Integer combinationCnt = combinations.get(negative);
42
if (combinationCnt != null) {
43
dfs((1 << N) - 1, subsets.size(), cnt + combinationCnt);
44
}
45
46
for (int i = index + 1; i < subsets.size(); i++) {
47
if (cnt + 1 >= answer) {
48
return;
49
}
50
51
Integer subset = subsets.get(i);
52
if ((set & subset) != 0) {
53
continue;
54
}
55
56
Integer combination = set | subset;
57
combinations.putIfAbsent(combination, cnt + 1);
58
dfs(combination, i, cnt + 1);
59
}
60
return;
61
}
62
63
public static void main(String args[]) throws IOException {
64
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
65
StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
66
N = Integer.parseInt(stringTokenizer.nextToken());
67
answer = N;
68
M = Integer.parseInt(stringTokenizer.nextToken());
69
70
DNAs = new ArrayList<>(N);
71
for (int i = 0; i < N; i++) {
72
stringTokenizer = new StringTokenizer(bufferedReader.readLine());
73
String DNA = stringTokenizer.nextToken();
74
DNAs.add(DNA);
75
superDNAs.put((1 << i), DNA);
76
}
77
78
// 예를 들어 3개면 111
79
// (1 << 3) - 1 부터 0까지
80
// int max = (1 << N);
81
for (int i = 0; i < (1 << N); i++) {
82
// 돼 문자열, 안돼 ""
83
List<Integer> subset = getSubset(i);
84
// 되는지 판단해서 넣는다.
85
String superDNA = mergeDNA(subset);
86
if (superDNA != "") {
87
subsets.add(i);
88
}
89
}
90
91
for (Integer subset : subsets) {
92
combinations.put(subset, 1);
93
}
94
95
Collections.reverse(subsets);
96
for (int i = 0; i < subsets.size(); i++) {
97
dfs(subsets.get(i), i, 1);
98
}
99
System.out.println(answer);
100
}
101
102
private static List<Integer> getSubset(final int combination) {
103
List<Integer> subset = new ArrayList<>();
104
for (int i = 0; i < N; i++) {
105
if ((combination & (1 << i)) == 0) {
106
continue;
107
}
108
109
subset.add(i);
110
}
111
return subset;
112
}
113
114
// subset get은 DNA의 인덱스임을 명심
115
private static String mergeDNA(List<Integer> DNAIndex) {
116
if (DNAIndex.size() == 0) {
117
return "";
118
}
119
120
// 15 * 3만 2천
121
int mergeNumber = (1 << DNAIndex.get(0));
122
StringBuilder superDNA = new StringBuilder(superDNAs.get(mergeNumber));
123
124
for (int i = 1; i < DNAIndex.size(); i++) {
125
mergeNumber |= (1 << DNAIndex.get(i));
126
String discoveredDNA = superDNAs.get(mergeNumber);
127
if (discoveredDNA != null) {
128
if (discoveredDNA == "") {
129
return "";
130
}
131
132
superDNA = new StringBuilder(discoveredDNA);
133
continue;
134
}
135
136
String DNA = DNAs.get(DNAIndex.get(i));
137
for (int j = 0; j < M; j++) {
138
if (superDNA.charAt(j) == DNA.charAt(j)) {
139
continue;
140
}
141
142
if (superDNA.charAt(j) != '.' && DNA.charAt(j) != '.') {
143
superDNAs.putIfAbsent(mergeNumber, "");
144
return "";
145
}
146
147
char newChar = superDNA.charAt(j);
148
if (newChar == '.') {
149
newChar = DNA.charAt(j);
150
}
151
superDNA.replace(j, j + 1, String.valueOf(newChar));
152
}
153
superDNAs.putIfAbsent(mergeNumber, superDNA.toString());
154
}
155
156
superDNAs.putIfAbsent(mergeNumber, superDNA.toString());
157
return superDNA.toString();
158
}
159
}