백준 1512번: 주기문으로 바꾸기

문제

https://www.acmicpc.net/problem/1512

DNA 문자열의 길이 $L$ , 주기의 길이 $P$
- DNA 문자열은 A, C, G, T로만 구성, 문자열의 길이 $L$ 은 3000보다 작거나 같음
$0 \le i \le L - P - 1$ 인 모든 $i$ 에 대해 $i + p$ 위치에 있는 문자가 같으면 '주기문'이라고 함
$L$ 보다 작거나 같은 $M$ 이 주어짐
DNA 문자열을 $M$ 보다 작거나 같은 주기로 이루어진 주기문으로 바꿀 때 바꾸는 문자열의 개수가 최소일 때 그 수를 출력

시도 1

접근 방법

dns[0:M]이 주기문, dna[M:] 문자열에서 주기문과 다른 알파벳이 몇 개 있는지 카운트
M-1, M-2, ..., 1로 주기문 길이를 바꿔가며 반복
이 중 바꿔야 할 문자 개수가 최소가 되는 경우를 반환

코드

import sys

r = sys.stdin.readline
M = int(r())
dna = r().strip()
L = len(dna)

answer = []
while M > 0:
    pattern, s = dna[:M], dna[M:]
    cnt = 0
    while s:
        p = pattern[:len(s)]
        for a, b in zip(p, s):
            if a != b:
                cnt += 1
        s = s[M:]

    answer.append(cnt)
    M -= 1

print(min(answer))

결과

틀림?? 왜지!!!!!

시도 2

오답 원인 분석, 새 접근법

'주기문'에 꽂혀서 문자열에서 주기문을 찾으려 했지만 이게 아닌 것 같다. 문제 내용에 충실하게 생각을 다시 해보자.
$0 \le i \le L - P - 1$ 인 모든 $i$ 에 대해 $i + p$ 위치에 있는 문자가 같다고 했으니,
- 만약 $M$ = 3이라면 0, 3, 6, 9...번째 문자가 같아야 되고, 1, 4, 7...번째 문자도 같아야 한다.
- 0, 3, 6, 9...번째에 등장한 문자 개수를 세고, 그 중 제일 많은 문자에 맞춰 나머지 문자를 바꾸면 변경할 문자 수가 제일 적을 것.
- 그렇게 다 바꾸고 나서 "dna'[:M]이 주기다"라고 하자 ~~(선 조치 후 보고)~~

그러니 다시 설명하자면, 기존에는 '주기문'을 찾고 이를 나머지 문자열과 비교하는 데 집중했다면

dna = ACGTGCA, M = 2 => dna[:2] = AC
dna'= ACACACA
         XXOXOXX => 3

이번 시도는 적게 바꾸는 것을 우선하고, 바뀐 문자열에서 주기를 찾는 것 (사실 주기문을 찾을 필요도 없긴 하다. 바뀐 문자 개수가 중요할 뿐...)

dna = ACGTGCA, M = 2
even = AGGA => A: 2, G: 2 => G를 A로 변경
odd = CTC => C: 2, T: 1 => T를 C로 변경
dna' = ACACACA
dna'[:2] = AC

수정 코드

import sys

r = sys.stdin.readline
M = int(r())
s = r().strip()

answer = 9999
while M > 0:
    cnt = 0
    for i in range(M):
        d = {k: 0 for k in "ACGT"}
        for c in s[i::M]:
            d[c] += 1
        v = d.values()
        cnt += sum(v) - max(v)
    answer = min(answer, cnt)
    M -= 1

print(answer)

결과

길이가 3000까지인데다 for문이 많이 중첩되어 시간이 꽤 오래 걸렸으나 통과. 주기문을 찾아야 된다는 생각에 갇혀서 많이 틀려버렸지만, 결국 성공해서 다행이다.