[백준-파이썬] 1195: 킥다운

문제 보러 가기!

문제와 함께 하는 즐거운 크리스마스 이브 ~

구해야 하는 것은 두 기어가 주어졌을 때 맞물리게 하는 가장 짧은 가로 너비이다. 즉 맞물리는 최대 길이를 찾으면 된다. (두 기어의 길이 합에서 맞물리는 최대 길이를 빼면 정답이 된다.)

part1, part2에 오는 문자들의 개수가 적어서, 일일이 다 봐주었다!

두 기어가 맞물리는지, 아닌지 봐줄 때 아래 세 가지 경우를 봐줄 수 있다.

 

1번, 2번 경우이다.

노란색 왼쪽이 1번, 오른쪽이 2번 경우이다.

1번) 짧은 기어를 기준으로, 짧은 기어가 긴 기어 왼쪽에서 하나씩 더 겹쳐지면서, 그럴 때 맞물리는지 볼 수 있다.

2번) 짧은 기어가 긴 기어 오른쪽에서 하나씩 더 겹치지면서, 그럴 때 맞물리는지 볼 수 있다.

-> 맞물리면 그때까지의 최대 맞물리는 길이와 비교해서, 업데이트한다.

3번 경우는 짧은 기어가 긴 기어 안에 포함되는 경우이다. 이럴 때는 일단 한번이라도 맞물린다면, 더이상 봐줄 필요가 없으니까 break한다.

 

맞물리는지 아닌지 판단하는 것도 중요하다. 처음에는 둘이 무조건 기어 파트가(이, 홈) 달라야 한다고 했더니 틀렸다. 그렇게 생각하면 예제도 해석이 안됐다..

그림을 잘 보니까, 무조건 다를 필요는 없는 것이었다.

홈-이: 당연히 ok

이-이: 둘 다 튀어나와서 no.

홈- 홈: 둘 다 들어갔으면 ok.

그래서 둘 다 이-이 일 경우만 맞물리지 않는 걸로 했다.

 

인덱스 부분을 실수해서 몇 번 틀렸다..!

import sys

input = sys.stdin.readline

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

if len(part1) > len(part2):
    part1, part2 = part2, part1
    # 1이 짧은 기어가 되게 함.

meet_thing = 0
for k in range(len(part1)):
    # 짧은 게 앞에서부터 출발해서, 한칸씩 겹쳐보면서 맞물리는지 보기.
    for i in range(k+1):
        if part1[-k+i-1] == '2' and part2[i] == '2':  # 둘 다 '이'(나온 부분)면 맞물리지 않는다는 뜻
            break
    else:  # 맞물리면
        meet_thing = max(meet_thing, k + 1)  # 맞물리는 갯수 업데이트

    # 짧은 게 뒤에서부터 출발해서, 한칸씩 겹쳐보면서 맞물리나 보기
    for i in range(k+1):
        if part1[i] == '2' and part2[-k+i-1] == '2':  # 둘 다 '이'(나온 부분)면 맞물리지 않는다는 뜻
            break
    else:  # 맞물리면
        meet_thing = max(meet_thing, k + 1)  # 맞물리는 갯수 업데이트

# 짧은 게 긴 거랑 만나는 지점 앞에서부터 출발해서, 한칸씩 앞으로 가면서 맞물리는지 보기-> 하나라도 ok되면 긴 것 길이가 정답
for k in range(len(part2) - len(part1) + 1):
    for i in range(len(part1)):
        if part1[i] == '2' and part2[i + k] == '2':  # 둘 다 '이'(나온 부분)면 맞물리지 않는다는 뜻
            break
    else:  # 맞물리면
        meet_thing = max(meet_thing, len(part1))  # 맞물리는 갯수 업데이트
        break  # 하나라도 되면 그만 봐도 됨(어차피 정답은 part2 길이)

print(len(part1) + len(part2) - meet_thing)