문제
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로 주기문 길이를 바꿔가며 반복- 이 중 바꿔야 할 문자 개수가 최소가 되는 경우를 반환
코드
1import sys
2
3r = sys.stdin.readline
4M = int(r())
5dna = r().strip()
6L = len(dna)
7
8answer = []
9while M > 0:
10 pattern, s = dna[:M], dna[M:]
11 cnt = 0
12 while s:
13 p = pattern[:len(s)]
14 for a, b in zip(p, s):
15 if a != b:
16 cnt += 1
17 s = s[M:]
18
19 answer.append(cnt)
20 M -= 1
21
22print(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]이 주기다"라고 하자(선 조치 후 보고)
그러니 다시 설명하자면, 기존에는 ‘주기문’을 찾고 이를 나머지 문자열과 비교하는 데 집중했다면
1dna = ACGTGCA, M = 2 => dna[:2] = AC
2dna'= ACACACA
3 XXOXOXX => 3
이번 시도는 적게 바꾸는 것을 우선하고, 바뀐 문자열에서 주기를 찾는 것 (사실 주기문을 찾을 필요도 없긴 하다. 바뀐 문자 개수가 중요할 뿐…)
1dna = ACGTGCA, M = 2
2even = AGGA => A: 2, G: 2 => G를 A로 변경
3odd = CTC => C: 2, T: 1 => T를 C로 변경
4dna' = ACACACA
5dna'[:2] = AC
수정 코드
1import sys
2
3r = sys.stdin.readline
4M = int(r())
5s = r().strip()
6
7answer = 9999
8while M > 0:
9 cnt = 0
10 for i in range(M):
11 d = {k: 0 for k in "ACGT"}
12 for c in s[i::M]:
13 d[c] += 1
14 v = d.values()
15 cnt += sum(v) - max(v)
16 answer = min(answer, cnt)
17 M -= 1
18
19print(answer)
결과
길이가 3000까지인데다 for문이 많이 중첩되어 시간이 꽤 오래 걸렸으나 통과. 주기문을 찾아야 된다는 생각에 갇혀서 많이 틀려버렸지만, 결국 성공해서 다행이다.
Comments