백준 1195(킥다운) - 해결

킥다운

 

문제

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

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

 

입력

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

 

출력

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

---

처음에 쉽게 구할 수 있을거 같은데 뭔가 걸리는 부분이 많았다.

맞물리는 구간 구하는 건 구하는데 길이를 같이 구해야해서 뭔가 막히는 부분이 있었다.

그래서 생각한 것이 부분을 나눠서 하는 방법이다.

큰 파트 왼쪽에 작은 파트가 올 때, 큰 파트 안에 작은 파트가 있을 때, 큰 파트 오른쪽에 작은 파트가 올 때.

이렇게 나눠서 생각하였다.

그리고 맞물린 다는 건 둘 다 이만 아니면 되는 거라 처음 이 부분에서 틀렸다.

import sys
input = sys.stdin.readline

part1 = list(input().strip())
part2 = list(input().strip())

# 길이 비교
if len(part1) >= len(part2):
    long_part = part1
    short_part = part2
else:
    long_part = part2
    short_part = part1

# 한칸씩 앞으로 가면서 확인하기 위해서 빈칸은 0으로
check_part = ['0'] * (len(short_part) - 1) + long_part[:] + ['0'] * (len(short_part) - 1)

total_len = len(short_part) + len(long_part)
# 몇번째에서 시작하는지
index = -1
# 최소 길이 
result = total_len

# 작은 파트가 왼쪽에 있을 때
for i in range(len(short_part) - 1):
    # 한 칸씩 앞으로
    index += 1
    # 길이는 줄어듦
    total_len -= 1
    # 맞물림 확인
    for j in range(len(short_part)):
        # 둘다 이 면 맞물릴 수 없기 떄문에
        if check_part[index + j] == '2' and short_part[j] == '2':
            break
    # 맞물리는 경우 길이 확인
    else:
        if result > total_len:
            result = total_len

total_len -= 1
# 작은 파트가 큰 파트내에 있을 때
for i in range(len(long_part) - len(short_part) + 1):
    index += 1
    # 길이는 줄어들지 않고 긴 파트에 고정되기 떄문에

    for j in range(len(short_part)):
        if check_part[index + j] == '2' and short_part[j] == '2':
            break
    else:
        if result > total_len:
            result = total_len

# 작은 파트가 오른쪽으로 갈 때
for i in range(len(short_part) - 1):
    index += 1
    # 길이는 늘어남
    total_len += 1
    for j in range(len(short_part)):
        if check_part[index + j] == '2' and short_part[j] == '2':
            break
    else:
        if result > total_len:
            result = total_len

print(result)