문제
DNA 서열은 'A', 'G', 'T', 혹은 'C' 4글자로 이뤄진 서열을 말한다.
임의의 DNA 서열 A, B에 대해 B를 뒤집은 다음, B의 뒤집힌 보수의 형태 (reverse complementary form)를 취했을 때, A와 같을 경우 2개의 DNA서열을 서로 동치한다고 한다.
'뒤집힌 보수의 형태' 란 DNA 서열 s를 뒤에서 앞으로 읽는 형태로 바꾼 다음, 각 문자에 대해 보수를 취해준 형태를 뜻한다. 여기서 보수란 문자 'A'는 'T'로, 'T'는 'A'로, 'G'는 'C'로, 'C'는 'G'로 치환된 서열을 뜻한다.
예를 들어 DNA 서열 ACGTA를 뒤집었을 경우 ATGCA가 되며, 이를 보수로 치환하면 TACGT가 된다. 따라서 ACGTA 뒤집힌 보수의 형태는 TACGT이며, ACGTA와 TACGT는 동치 관계에 있다.
서로 다른 DNA 서열이 주어졌을 때, 동치 관계에 있는 DNA 서열이 존재하지 않는 부분 집합 중 원소의 개수가 가장 큰 부분 집합을 찾는 프로그램을 작성하라.
입력
첫번째 줄에는 DNA 서열의 개수 N(1≤N≤50)이 입력된다. 그 다음줄 부터 N개의 줄에는 길이 50 이하의 DNA 서열이 입력된다. DNA서열은 문자 'A', 'G', 'T', 'C'로 이뤄져 있으며, 입력된 DNA 서열이 동일한게 2개 이상 존재할 수 없다.
출력
동치 관계가 존재하지 않는 부분집합의 원소의 최대 개수를 출력한다.
예제
4
ACGCGCGTA
GTCGATGCA
ACGTAGCT
TACGCGCGT
3
힌트
로그인해야 코드를 작성할 수 있어요.