[BOJ] 7977번 크리스 마틴

[BOJ] 7977번 크리스 마틴 문제

굉장히 흥미로웠던 문제다. 이 문제를 알기 위해서는 최장 공통 부분 수열(LCS; Longest Common Subsequence)를 알아야한다. 몰라도 어찌어찌 풀 수는 있겠지만, 당연하게도 LCS 알고리즘을 알면 풀기 더 쉽다.

---

LCS 알고리즘은 두 개의 길이가 다른 문자열이 있을 때, 공통적으로 존재하는 최대 부분 문자열을 구하는 알고리즘이다. 정확히는 다이나믹 프로그래밍(Dynamic Programming)의 일종이며, 그림을 보면서 이해하기가 쉽기 때문에 그렇게 막 어려운 알고리즘은 아니다.

• 관련 문제 - [BOJ] 9251번 LCS 문제

이 알고리즘의 핵심은 같은 문자일 때에는 모든 방향에서의 이전 DP 값에서 1을 더한 값을 저장하고, 아닌 경우에는 인접한 두 값 중 큰 값을 저장한다는 것이다. 우리는 이걸 이 문제에 잘 이용해야한다.

이 문제의 핵심은 이 LCS 알고리즘을 적용시켰을 때 유사도가 가장 적은, 즉 최대 LCS의 값이 적은 문자열을 만들어내야 한다는 것이다.

결국 이 조건을 만족하는 문자열은 입력으로 주어진 문자열 중에서 가장 적은 개수의 문자만으로 이루어진 문자열이 되고, 만족하는 길이 n은 해당 문자가 입력의 문자열에 있는 개수가 된다.

예시로 주어진 'GACT'에 대한 정답은 n = 1이며, 'AAAA', 'TTTT', 'GGGG', 'CCCC' 모두 정답이 된다. 잘 이해가 안된다면 LCS 알고리즘을 조금 더 공부하고 고민해보자.

import sys

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    dna = sys.stdin.readline().rstrip()
    atgc = [dna.count('A'), dna.count('T'), dna.count('G'), dna.count('C')]
    min_atgc = min(atgc)
    print(min_atgc)
    if atgc[0] == min_atgc:
        print('A'*N)
    elif atgc[1] == min_atgc:
        print('T'*N)
    elif atgc[2] == min_atgc:
        print('G'*N)
    else:
        print('C'*N)