[백준] 1195번 - 킥다운 (파이썬) 문제 및 풀이

문제) 백준 - 구현(Implementation) - 킥다운

-> www.acmicpc.net/problem/1195

1195번: 킥다운

입력 첫 줄에는 첫 번째 기어 파트, 두 번째 줄에는 두 번째 기어 파트가 1,2로 구성된 문자열이 주어진다. 1은 홈(들어간 부분), 2는 이(튀어나온 부분)를 의미한다. 먼저 너비를 구하기 전에 어떤 경우에 기어가 맞물릴 수 있는지 알아보자.

 

 

①: 짧은 기어 파트가 1이고 긴 기어 파트가 2일 때, 서로 맞물려 기어를 끼울 수 있다.

②: 긴 기어 파트가 1이고 짧은 기어 파트가 2일 때, 서로 맞물려 기어를 끼울 수 있다.

③: 짧은 기어 파트가 1이고 긴 기어 파트가 1일 때, 서로 맞물리지는 않지만 기어를 끼우는데 지장을 주지 않는다.

위의 세 경우는 기어를 끼우는데 지장을 주지 않는다. 따라서 우리는 둘의 기어 파트가 '2'일 경우만 확인해서 존재하는 경우를 제외하고 최솟값을 계산하면 된다.

 

 

Step 1)

짧은 기어를 기준으로 앞에서 부터 하나 씩 인덱스를 늘려주어 비교한다.

	사이클 1	사이클 2	...	사이클 i
짧은 기어	(-1)	(-2, -1)	...	short[(-1) * i +j]
긴 기어	(0)	(0,  1)	....	long[j]

 

Step 2)

짧은 기어를 기준으로 앞에서 부터 하나 씩 인덱스를 늘려주어 비교한다.

	사이클 1	사이클 2	...	사이클 i
짧은 기어	(0)	(1, 0)	...	short[i - 1 -j]
긴 기어	(-1)	(9, 8)	...	long[len(long) - 1 - j]

 

Step 3)

짧은 기어를 긴 기어의 범위 안에 비교하여 인덱스를 조절하여 비교한다.

	사이클 1	사이클 2	...	사이클 i
짧은 기어	(0, ... , 6)	(0, ... , 6)	...	short[j]
긴 기어	(0, ... , 6)	(1, ... , 7)	...	long[j + i - 1]

 

Step 1,2,3을 하나 씩 비교해주며 킥다운 장치의 최솟값을 갱신해나가면 구해주면 된다.

 

 

 

소스 코드)

import sys

input = sys.stdin.readline

long_str = input().rstrip()
short_str = input().rstrip()
if len(short_str) > len(long_str):
    long_str, short_str = short_str, long_str

result = len(short_str) + len(long_str)
switch = True

for i in range(len(short_str)):
    # Step 1
    for j in range(i + 1):
        if long_str[j] == '2' and short_str[(-1) * (i + 1) + j] == '2':
            switch = False
            break

    if switch:
        result = min(result, len(long_str) + len(short_str) - (i + 1))

    switch = True
    # Step 2
    for j in range(i + 1):
        if long_str[len(long_str) - 1 - j] == '2' and short_str[i - j] == '2':
            switch = False
            break

    if switch:
        result = min(result, len(long_str) + len(short_str) - (i + 1))
    switch = True

switch = True
for i in range(len(long_str) - len(short_str)):
    # Step 3
    for j in range(len(short_str)):
        if short_str[j] == '2' and long_str[j + i] == '2':
            switch = False
            break
    if switch:
        result = min(result, len(long_str))
    switch = True

print(result)