백준 1195번 - 킥다운
문제 풀이
s1을 짧은 기어, s2를 긴 기어로 두고 s2를 중심으로 s1을 가지고 s2의 왼쪽에서, 오른쪽에서, 안쪽에서 슬라이딩 해보면서 기어가 맞물릴 수 있는지 확인한다.
단순히 2와 2가 만나는 경우를 제외하고는 다 맞물릴 수 있다고 간주한다.
ans의 기본 최대값은 s1의길이 + s2의 길이다. 이 점을 놓쳐서 애먹었음.
문제 링크
소스코드
#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;
}
Author And Source
이 문제에 관하여(백준 1195번 - 킥다운), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@pjh612/백준-1195번-킥다운저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)