Mingssssss

1. 문제

어떤 문자열 A를 타이핑하려고 한다.

그냥 한 글자씩 타이핑 한다면 A의 길이만큼 키를 눌러야 할 것이다.

여기에 속도를 조금 더 높이기 위해 어떤 문자열 B가 저장되어 있어서 키를 한번 누른 것으로 B전체를 타이핑 할 수 있다.

이미 타이핑 한 문자를 지우는 것은 불가능하다.

예를 들어 A=”asakusa”, B=”sa”일 때, 다음 그림과 같이 B를 두 번 사용하면 5번 만에 A를 타이핑 할 수 있다.

A와 B가 주어질 때 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 구하여라.

[입력]

첫 번째 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스마다 첫 번째 줄에 두 문자열 A, B가 주어진다. A의 길이는 1이상 10,000이하, B의 길이는 1이상 100이하이다.

[출력]

각 테스트 케이스마다 A 전체를 타이핑 하기 위해 키를 눌러야 하는 횟수의 최솟값을 출력한다.

2. 코드

import sys
sys.stdin = open('input.txt')

T = int(input())
for tc in range(T):
    N, M = map(str, (input().split()))

    result = 0
    cnt = 0

    for i in range(len(N)-len(M)+1):
        if N[cnt:len(M)+cnt] == M:
            result += 1
            cnt = len(M)+cnt - 1
        cnt += 1
    result = len(N) - result*len(M) + result

    print('#{0} {1}'.format(tc+1, result))

3. 리뷰

D4 문제지만 난이도가 D2급인 것 같다. 받은 문자열이 주어진 문자열에 포함되어 있으면
해당 문자열을 지워주고 cnt를 추가하여 최솟값을 반환했다.
포함 될 때마다 1씩 카운트 하는 것만주의하면 쉽게 풀 수 있었던 문제였다.