[백준] 2806 DNA 발견

문제소개

---

2806 DNA 발견은 DP 문제 입니다. 개인적으로는 DP를 좋아합니다. 

점화식 세우거나 규칙을 찾는게 재밌습니다 ㅎㅎ;;

보통 메모제이션할 배열을 하나만 생각하는데 익숙한데

해당 문제는 A와 B에 대한 메모제이션을 생각하면 쉽게 풀 수 있습니다.

 

문제해결

---

DNA의 돌연변이 규칙이 점화식 세우는데 단서가 됩니다.

1) DNA에서 1개만 바꿀 수 있다.

2) 1번 부터 K번까지 한번에 바꿀 수 있다. 

 

A[i] = 1번 부터 i번까지 A로 만드는 최소 돌연변이 횟수

B[i] = 1번 부터 i번까지 B로 만드는 최소 돌연변이 횟수라고 하면 

 

A[i] = A[i-1] 또는 B[i -1] + 1  (2번 규칙을 적용) 이 된다는 것을 찾을 수 있습니다.

 

---

소스보기