취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25276번 문제인 Sperhling이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25276 

왼쪽 키를 누르고 나중에 다시 오른쪽 키를 눌러 커서를 돌려놓으나 백스페이스를 눌러 문자를 지우고 나중에 다시 각 문자를 입력해넣으나 키를 누르는 횟수는 같다는 점을 관찰하자.

위 관찰에 의해, 기존 상태의 문자열을 "앞에서부터 제대로 친 부분"만을 남기고 모두 지운 후 "올바른 문자열"을 그 뒤로 새로 타이핑하는 것이 최소 횟수로 문자열을 수정하는 방법 중 하나임을 알 수 있다.

두 문자열의 맨 앞에서부터의 공통부분 길이와 각 문자열의 길이를 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <string>
using namespace std;

string s1, s2;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> s1 >> s2; s1 += '.', s2 += '!';
	int idx = 0;
	while (s1[idx] == s2[idx]) idx++;
	cout << s1.length() + s2.length() - idx * 2 - 2;
}