[BOJ] 1195 - 킥다운

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

BOJ - 킥다운

문제 유형: 문자열 처리, 완전 탐색

문제 난이도: Silver I

시간 제한: 2초

메모리 제한: 128MB

 

문제

세계적으로 유명한 엄지민 자동차 회사는 효율적인 킥다운 장치를 만들어달라는 의뢰를 받았다. 킥다운이란 자동차에서 낮은 기어로 바꾸는 장치를 의미한다. 연구 끝에 효율적인 킥다운 장치는 '이'와 '홈'이 불규칙하게 배열되어 있는 기어로 만들어져야 한다는 것을 알았다.

첫 번째 그림과 같이 두 기어 파트가 서로 마주보고 있게 된다. 튀어나온 것이 기어의 이, 들어간 곳이 홈이다. 그리고 이들을 두 번째 그림과 같이 서로 맞물리게 끼우는 것으로 킥다운 장치를 만들 수 있다. 하지만 문제는 맞물리게 하였을 때 가로 너비가 짧을수록 효율적인 킥다운 장치가 된다. 때문에 문제는 두 기어가 주어졌을 때 맞물리게 하는 가장 짧은 가로 너비를 구하는 것이다.

 

입력

첫 줄에는 첫 번째 기어 파트를 나타내는 1과 2로 구성된 문자열이 주어진다. 두 번째 줄에는 마찬가지로 두 번째 기어 파트를 나타내는 1, 2로 구성된 문자열이 주어진다. 여기서 1은 홈을, 2는 이를 의미한다. 길이 <= 100

 

출력

첫 줄에 만들 수 있는 가장 짧은 가로 너비를 출력한다.

 

풀이

두 가지의 경우가 있다.

첫 줄을 두 번째 줄에 맞춰보는 경우, 두 번째 줄을 첫 줄에 맞춰보는 경우.

각 경우에 따라 아래 그림처럼 시작해서, 오프셋을 지정해서 밀면서 비교해보면 된다.

유효한지는, b를 기준으로 배열을 돌아주면 된다.

b[i]에 대해서 a의 대응되는 인덱스는 a[offset + i]이다.

근데, offset + i가 유효한 범위를 벗어난 경우는 그냥 지나가고, 

0 <= offset + i < n(a의길이)인경우에만 b[i]와 비교해주면 된다.

둘다 '2'인경우가 한 번이라도있다면, 불가능한 경우다.

정상적으로 순회를 성공했다면, 가장 짧은 길이를 업데이트 한다.

오른쪽의 끝은 max(n, offset + m), 왼쪽의 끝은 min(0, offset)이다.

오른쪽에서 왼쪽을 빼주면 된다.

 

size()로 나온 값은 size_t이므로, unsigned값이라 조심해야 한다. 의도치 않은 비교가 일어날 수 있다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

bool isFit(const string &a, const string &b, int o) {
  int n = a.size();
  int m = b.size();
  for (int i = 0; i < m; ++i) {
    if (o + i < 0)
      continue;
    if (o + i >= n)
      continue;
    if (a[o + i] == '2' && b[i] == '2')
      return false;
  }
  return true;
}

int minMatchSize(string a, string b) {
  int n = a.size();
  int m = b.size();
  int res = a.size() + b.size();
  int start = b.size() * -1 + 1;
  int end = a.size();
  for (int o = start, i = 1; o < end; ++o, ++i) {
    if (isFit(a, b, o)) {
      int len = max(n, o + m) - min(0, o);
      res = min(res, len);
    }
  }
  return res;
}

int main(int argc, char *argv[]) {
  string s1, s2;

  cin >> s1 >> s2;

  int res1 = minMatchSize(s1, s2);
  int res2 = minMatchSize(s2, s1);

  cout << min(res1, res2) << "\n";

  return 0;
}