백준 2195 - 문자열 복사

문제 설명

어떤 원본 문자열 S가 주어졌을 때, 이 문자열의 부분을 복사하여 P라는 새로운 문자열을 만들려고 한다. 복사를 할 때에는 copy(s, p) 이라는 함수를 이용하는데, 이는 S의 s번 문자부터 p개의 문자를 P에 복사해서 붙인다는 의미이다.

예를 들어 S="abaabba", P="aaabbbabbbaaa"인 경우를 생각해 보자. 이때는 copy(3, 2), copy(4, 3), copy(2, 2), copy(5, 2), copy(2, 3), copy(1, 1) 를 수행하여 P를 만들 수 있다. 각 단계별로 P는 "aa", "aaabb", "aaabbba", …와 같이 변하게 된다.

이와 같은 copy 연산을 이용하여 S에서 P를 만들려고 하는데, 이때 가능하면 copy 함수를 조금 사용하려고 한다.

S와 P가 주어졌을 때, 필요한 copy 함수의 최소 사용횟수를 구하는 프로그램을 작성하시오.

https://www.acmicpc.net/problem/2195

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, S와 P가 주어질 때 S의 substring을 적절히 조합해 P를 만들 때 최소한의 substring의 개수를 구해야 한다.

 

해당 문제는 S에서 P를 만드는 것보다 P에서 S로 변환한다고 생각하면 훨씬 쉽게 풀 수 있다.

P의 맨 끝부터 S에 존재하는지 여부를 확인하며 하나씩 문자를 늘려가면 된다.

예를 들어, S = "abaabba", P = "aaabbbabbbaaa"라고 가정해 보자.

우선, P의 제일 끝 문자인 'a'를 S에서 찾는다.

'a'는 S에 존재하므로 하나를 추가해 "aa"를 S에서 찾는다.

"aa"역시 S의 substring이다.

그럼 "aaa"를 찾지만 존재하지 않는다.

따라서, "aa"를 복사하는 연산을 1회 해야 한다.

위와 같은 연산을 계속해서 반복하면 된다.

 

그렇다면 특정 문자열이 S에 존재하는지 여부를 판단하는 것은 std::string의 함수인 find를 이용하면 쉽다.find는 substring이 처음 나타나는 위치를 반환한다.만약, 존재하지 않는다면 string::npos를 반환하기 때문에 이를 이용하면 간단하게 구현할 수 있다.

bool IsSubstr(const string& str)
{
    auto result = S.find(str);
    return result != string::npos;
}

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

string S, P;

bool IsSubstr(const string& str)
{
    auto result = S.find(str);
    return result != string::npos;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> S >> P;

    int ans = 0;
    for (int i = P.length() - 1; i >= 0; i--)
    {
        string str;
        str += P[i];

        int offset = 0;
        while (IsSubstr(str))
        {
            offset++;
            if (i - offset < 0) break;
            str = P[i - offset] + str;
        }
        offset--;

        i -= offset;
        ans++;
    }

    cout << ans;

    return 0;
}

---