[백준 11008] 복붙의 달인

문제출처: https://www.acmicpc.net/problem/11008

문제

한신이는 대학교에서 "복붙의 달인"으로 유명하다. 한신이는 타이핑 속도가 느리기 때문에 대학에서 가능한 모든 일을 복붙으로 해결한다. 그는 n개의 문자를 입력하는데 있어서 n초의 시간이 걸리지만 뛰어난 "붙여넣기" 스킬을 이용하면 어떠한 개수의 문자도 단 1초만에 타이핑 할 수 있다. 만약 한신이가 "bana"를 복사한 상태에서 "banana"를 타이핑한다면, "bana" 붙여넣기 1초, 'n' 입력, 'a' 입력으로 총 3초가 걸린다. 한신이가 클립보드에 저장한 p를 알고 있을 때 s를 입력하는데 걸리는 최소 시간을 계산해보자!

입력

첫 번째 줄에는 테스트케이스의 개수 T(T ≤ 25)가 입력된다. 각 테스트케이스는 한 줄에 2개의 문자열 s와 p가 공백으로 구분되어 입력되며 한신이는 p를 복사하여 s를 만들어 내는 것을 목표로 한다. s의 최대 길이는 10,000이고, p의 최대 길이는 100이다.

출력

각 테스트 케이스에 맞는 한신이가 p를 이용하여 s를 타이핑할 때 걸리는 최소 시간(초 단위)을 출력하라!

풀이

string에 부분문자열을 구할 수 있는 substr기능으로 쉽게 풀 수 있습니다. 정답을 구하기위해선 일단 비교연산을 최대 s.size()만큼 해야하겠죠?(15행) 그리고 18행을 보면, s의 현재인덱스~p.size()만큼의 문자열이 p라면 start변수에 p.size()만큼 더해야합니다.(복붙하고 다시 또 복붙할게있나 확인하는연산), 아니라면 start를 한칸 옮겨주면서 다시 비교합니다. 한번 비교를 끝내고 연산 횟수를 카운팅해주며 최소횟수를 출력하면됩니다.

코드

#include<iostream>
#include<string>
using namespace std;
int main()
{
	int t;
	cin >> t;
	string s, p;
	for (int i = 0; i < t; i++)
	{
		int ans = 0;
		cin >> s >> p;
		int start = 0;
		//최대 s크기만큼연산
		while (start<s.size())
		{
			//s의 현재 부분문자열이 p면
			if (s.substr(start, p.size()) == p)
				//p사이즈만큼 건너뜀
				start += p.size();
			//아니면,start를한칸 옮김
			else
				start++;
			//연산한번 하고나서 한번씩카운팅
			ans++;
		}
		cout << ans << endl;
	}
}

결과