이번 문제는 백준 골드 5 문제 문자열 복사 문제이다.
문제를 차근차근 한 번 읽어보자.
두 문자열이 주어지며, 각 문자열은 최대 1000의 길이를 갖는다.
이 때, S에서 부분 문자열을 뽑아 붙혀 P를 만든다.
S의 부분 문자열을 뽑는 최소 횟수를 구해달라고 한다.
문제의 조건이 그렇게 복잡하지는 않다.
단순 탐색
가장 먼저 드는 생각은 문자열을 단순히 훑는 것이다.
최소로 문자열을 뽑으려면, 한 번에 최대한 길게 뽑는 것이 좋다.
그러려면, 목표 문자열에 포인터를 두고 원 문자열과 겹치는 길이만큼
포인터를 옮겨가면서 단순히 탐색 해볼 수 있을 것 같다.
그럼 이중 for문일텐데 시간초과가 나지 않고 통과할 수 있을까?
단순히 생각해보았을 때 최악의 경우 O(N^2)인 것인데,
N이 최대 1000이라고 생각하면 최대 100만이니 괜찮을 것 같다.