문제 풀이

s1을 짧은 기어, s2를 긴 기어로 두고 s2를 중심으로 s1을 가지고 s2의 왼쪽에서, 오른쪽에서, 안쪽에서 슬라이딩 해보면서 기어가 맞물릴 수 있는지 확인한다.
단순히 2와 2가 만나는 경우를 제외하고는 다 맞물릴 수 있다고 간주한다.
ans의 기본 최대값은 s1의길이 + s2의 길이다. 이 점을 놓쳐서 애먹었음.

문제 링크

boj/1195

소스코드

PS/1195.cpp

#include <string>
#include <vector>
#include<iostream>
#include<memory.h>
#include<map>
#include<algorithm>
#include<queue>
#include<set>
#include<math.h>
using namespace std;


int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	string s1, s2;
	cin >> s1 >> s2;

	if (s1.length() > s2.length())
	{
		swap(s1, s2);
	}
	int ans = s1.length()+s2.length();
	for (int i = 0; i < s1.length(); i++)
	{
		int s1_len = s1.length();
		bool flag = false;
		for (int j = 0; j <= i; j++)
		{
			if (s2[j] =='2' && s1[s1_len - 1 - i+ j] == '2')
			{
				flag = true;
				break;
			}
		}
		if (!flag)
			ans = min(ans, (int)s1.length() + (int)s2.length() - 1 - i);
	}
	for (int i = 0; i < s1.length(); i++)
	{

		int s2_len = s2.length();
		bool flag = false;
		for (int j = 0;j<=i;j++)
		{
			if (s2[s2_len -1 -i+j] == '2' &&  s1[j]=='2')
			{
				flag = true;
				break;
			}
		}
		if (!flag)
			ans = min(ans, (int)s1.length() + (int)s2.length() - 1 - i);
	}

	for (int i = 0; i<s2.length()- s1.length(); i++)
	{
		bool flag = false;
		for (int j = 0; j < s1.length(); j++)
		{
			if (s1[j]=='2' && s2[i+j] == '2')
			{
				flag = true;
				break;
			}
		}
		if (!flag)
			ans = min(ans,(int)s2.length());
	}
	cout << ans;
}