[1일 1알고] B1 29732 Rick-Roll Virus

 

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

 

릭롤 바이러스가 전염된 후 이를 치료할 수 있는지를 확인해야합니다.

 

일단 전염을 시킨 뒤 전염당한 사람의 수를 계산해 M과 비교했습니다.

문자열 S에 즉시 반영시키면 결과가 오염되기 때문에 별도의 문자열 temp를 만든 뒤 이를 활용해 계산했습니다.

 

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    string S, temp;
    cin >> S;
    temp = S;
    for (int i = 0; i < N; ++i)
    {
        if (temp[i] == 'R')
        {
            for (int k = i - K; k <= i + K; ++k)
            {
                if (k >= 0 && k < N)
                {
                    S[k] = 'R';
                }
            }
        }
    }

    int cnt = 0;
    for (int i = 0; i < N; ++i)
    {
        if (S[i] == 'R')
            ++cnt;
    }

    if (cnt > M)
        cout << "No";
    else
        cout << "Yes";

    return 0;
}

문제의 주어진 시간이 넉넉하기 때문에 통과했지만, 다른 사람들의 풀이에는 0ms로 해결한 것도 있었기 때문에 최적화 방법을 생각해보았습니다.

 

먼저 좌, 우를 나누어 전염시키고 전염시키는 과정에서 temp의 R을 만난다면, 해당 R은 더 멀리있는 곳을 전염시킬 것이기 때문에 루프를 break하는 생각을 했습니다.

 

그러고보니 계산을 범위 구간의 합으로 하면 된다고 생각이 들었고, 굳이 String 배열에 값을 바꿔갈 필요가 없다고 생각이 들었습니다.

 

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M, K;
    cin >> N >> M >> K;

    string S;
    cin >> S;

    int cnt = 0;
    int right = -1;

    for (int i = 0; i < N; ++i)
    {
        if (S[i] != 'R')
            continue;

        int L = max(0, i - K);
        int R = min(N - 1, i + K);

        if (L > right)
        {
            cnt += R - L + 1;
            right = R;
        }
        else if (R > right)
        {
            cnt += R - right;
            right = R;
        }
    }

    if (cnt > M)
        cout << "No";
    else
        cout << "Yes";

    return 0;
}

범위는 이전 범위와 겹치는 경우와 겹치지 않는 경우를 나누어 계산하면 간단합니다.

 

 

해당 방식으로 제출 후 시간이 줄어들었음을 확인했습니다.