블로그 이사 중입니다 >> gumgood.github.io

15483 최소 편집 본문

Problem Solving/문제 풀이

15483 최소 편집

gumgood 2018. 11. 13. 13:04

C++11


문자열을 각각 a, b라 했을 때,


dp[i][j] = 문자열 a[0~i]를 문자열 b[0~j]로 바꾸는데 드는 최소비용

(단, a[0], b[0]은 공백이라고 가정한다.)


dp[i][0]와 dp[0][i]는 공백에서 a[i]나 b[i]를 추가하는 비용이므로 dp[i][0] = dp[0][i] = i


dp[i][j]를 계산하기 위해 a[i]와 b[j]를 비교하면,


1) a[i] == b[j]인 경우

  a[i]와 b[j]를 매칭시켰을 때 연산이 필요없으므로 dp[i-1][j-1]의 비용과 동일하다.


2) a[i] != b[j]인 경우 

  다음과 같은 세가지 연산이 가능하다.

 2-1) 문자열 A에 마지막 문자 하나를 삽입하거나 (dp[i-1][j] + 1)


 2-2) 문자열 A에 마지막 문자 하나를 삭제하거나 (dp[i][j-1] + 1)


 2-3) 문자열 A에 마지막 문자 하나를 교체하거나 (dp[i-1][j-1] + 1)

'Problem Solving > 문제 풀이' 카테고리의 다른 글

1351 무한 수열  (0) 2018.11.13
11066 파일 합치기  (0) 2018.11.13
15483 최소 편집  (0) 2018.11.13
5430 AC  (0) 2018.11.13
1966 프린터 큐  (0) 2018.11.13
2164 카드2  (0) 2018.11.13
Tag
0 Comments
댓글쓰기 폼