개발/알고리즘
[백준] 2806 DNA 발견
고양이레옹이
2018. 11. 26. 15:17
728x90
반응형
문제소개
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번 규칙을 적용) 이 된다는 것을 찾을 수 있습니다.
728x90