백준 1055번 끝이없음

문제 링크입니다: https://www.acmicpc.net/problem/1055

처음에는 전부 시뮬레이션을 하는 실수를 한 뒤 bongssi님(http://bongssi.tistory.com/search/1055)의 해설을 보고 풀 수 있었던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 반복하는 횟수의 최대값이 매우 크기 때문에 직접 시뮬레이션을 하면 TLE 및 메모리 초과가 발생합니다.

-> 따라서, 재귀 함수를 통해 해당 인덱스에 무슨 알파벳이 있는지를 파악해야합니다.

2. '$'의 개수가 2 이상이면 30번만 반복해도 탐색하고자 하는 인덱스의 범위를 초과하기 때문에 반복하는 횟수를 줄일 수 있습니다.

3. 반복한 횟수를 기준으로 i 번째 인덱스에 위치한 알파벳을 찾기 위해 재귀함수를 이용합니다.

4. 반면, '$'의 개수가 2 미만일 경우 문자열의 길이가 증가하는 속도가 더디므로 직접 수식을 계산해 출력해줘야합니다.

#include <iostream>

#include <string>

using namespace std;

 

const int MAX = 31;

 

string s, input;

int dollar, nonDollar;

int repeat, start, finish;

//cache[i] = i번 반복했을 때 길이

long long cache[MAX]; //2 ^ 30 = 1,073,741,824

bool found;

 

void searchChar(int level, int idx) //level = 반복 횟수

{

        long long pos = 0;

        for (long long i = 0; !found && i < input.length(); i++)

        {

                 if (input[i] == '$')

                 {

                         //반복 횟수 기준으로 나눔

                         if (level == 1)

                         {

                                 if (idx <= pos + cache[level] - 1)

                                 {

                                          found = true;

                                          cout << s[idx - pos];

                                 }

                                 else

                                          pos += cache[level];

                         }

                         else if (level > 1)

                         {

                                 if (idx <= pos + cache[level] - 1)

                                          searchChar(level - 1, idx - pos);

                                 else

                                          pos += cache[level];

                         }

                 }

                 else

                 {

                         if (pos == idx)

                         {

                                 found = true;

                                 cout << input[i];

                                 return;

                         }

                         else

                                 pos++;

                 }

        }

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> s >> input >> repeat >> start >> finish;

 

        for (long long i = 0; i < input.length(); i++)

                 if (input[i] == '$')

                         dollar++;

                 else

                         nonDollar++;

 

        //$가 하나이면 길이가 천천히 증가하여 따로 처리

        if (dollar < 2)

        {

                 for (int i = start - 1; i < finish; i++)

                         if (i < s.length())

                                 cout << s[i];

                         else if (i >= s.length() + (input.length() - 1) * repeat)

                                 cout << "-";

                         //s.length() <= i < s.length() + (input.length() -1) * repeat

                         else

                                 cout << input[(i - s.length()) % (input.length() - 1) + 1];

                 cout << "\n";

        }

        //$가 2개부터이면 지수 비례하여 증가하므로 도중에 중단 가능

        else

        {

                 cache[1] = s.length();

                 for (int i = 2; i <= repeat; i++)

                 {

                         cache[i] = cache[i - 1] * dollar + nonDollar;

                         //구하고자 하는 인덱스 범위를 초과시 break

                         if (cache[i] > finish)

                         {

                                 repeat = i;

                                 break;

                         }

                 }

 

                 for (int i = start - 1; i < finish; i++)

                 {

                         int temp = repeat;

                         //범위 초과시

                         if (i >= cache[temp] * dollar + nonDollar)

                         {

                                 cout << "-";

                                 continue;

                         }

 

                         while (temp > 1 && cache[temp] > i)

                                 temp--;

 

                         found = false;

                         searchChar(temp, i);

                 }

                 cout << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~