문제 이해
요약
받은 두 수열을 가지고 띄어쓰기를 잘 조합하여,
가장 높은 점수를 받아내라는 것이 이 문제의 목표이다.
간과할 수 있는 점
두 수열은 '부분 수열'이다.
중간부터 시작할 수도 있다는 것이다.
예를 들어,
AB
B
가 있다면, 문제가 요구하는 답은 B가 될 것이다.
문제를 변형하자
-2와 3은 신경쓰지 말고 읽어보자.
뭔가 익숙하지 않는가?
그렇다. 최소 편집 거리 유형의 문제이다.
편집 거리 문제는 수열 2개 간에
추가
삭제
변경
냅두기
의 연산을 수행하여 두 수열을 같은 수열로 만들기 위한 최소의 편집 횟수를 구한다.
그런데 수열 A와 수열 B가 있고,
B를 A로 편집하는 입장에서 추가는 그저 추가로 느껴질 수 있지만,
둘을 동등한 관계에서 같이 편집해간다는 생각을 해보면,
A를 B로 편집하기 위한 삭제 연산으로 바라볼 수 있다.
이렇게 다른 관점으로 바라본 편집 거리 문제를 이 문제와 대조해보자.
문자를 공백과 대응시키는 연산은 삭제 연산과 동치이다.
문제 풀이
살짝 까다로울 수 있는 부분
역추적 과정이 필요하다.
각자의 방식이 있을 것이다.
1. from[] 배열을 만들어서 경로를 찾아나가는 방법
2. 도착 루트를 기준으로 그냥 백트래킹 식으로 역추적하는 방법(dp[] 배열의 상태를 알고 있을 경우 경로가 유일해질 때에 한함)
그냥 이 문제에서는 2번이 적용 가능하기에 2번을 적용했다.
점화식 정의하기
의 유사도라고 정의합시다.
이에 맞는 구현을 하는 것은 전혀 어렵지 않습니다.
다만 역추적 배열을 만들었을 경우에는 if문 투성이가 되어 약간 고생을 하셔야 됩니다.
코드와 구현
여기서부터 필자의 뻘짓 스토리...
읽지 않으셔도 됩니다...
저 같은 경우는, if (!dp[x.F][x.S]) return; 부분에서 약간 헤맸습니다.
dp의 값이 순간적으로 0이 되는 경우는 점수가 음수 밑으로 내려갈 것 같은 상황에 수열을 끊고 새로운 부분수열로 시작하는 경우가 해당됩니다. 그렇기 때문에 0인 경우까지 역추적에 포함시키면 안 되는 것인데, 저는 dp가 0이 되는 것의 의미를 제대로 이해하지 못하고 짜는 바람에 이런 불상사가 생겼습니다. 이렇게 쓰고 보니 역추적 배열을 만드는 것이 훨씬 낫겠군요...
코드 구현에 관한 질문은 댓으로 남겨주세요~!
끄읏
