[BAEKJOON] 백준 29732: Rick-Roll Virus (C#)

문제 링크

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

 

 

문제

2033년, 하루나라에서 밈 1위를 결정하고자 하는 투표에서 Rick Astley가 우승함과 동시에 하루나라에서 Rick-Roll Virus가 전염되고 있다. 이 바이러스에 감염되면 항상 Never gonna give you up을 흥얼거리기 때문에 haru_202는 이 바이러스를 막으려고 한다.

하루나라에 사는 𝑁명의 사람들은 일직선상에서 연속적으로 인접하여 살아가고 있으며, 𝑥=𝑖에 위치한 감염자는 1일 뒤 바이러스를 𝑥=max(1,𝑖−𝐾), ⋯, 𝑖, ⋯, min(𝑁,𝑖+𝐾)에 있는 사람들에게 전염시킨다.

 1일 뒤, haru_202가 치료제 𝑀개를 사용하여 Rick-Roll Virus에 감염된 사람을 모두 치료할 수 있는가? 단, 치료제는 1명에게 1개씩만 사용할 수 있다.

 

 

입력

첫 번째 줄에 정수 𝑁, 𝑀, 𝐾가 공백으로 구분되어 주어진다. (1≤𝑁≤10000; 0<𝑀≤𝑁; 0≤𝐾≤⌊𝑁2⌋)

두 번째 줄에 사람들의 감염 상태를 나타내는 길이 𝑁의 문자열 𝑆가 주어진다. 𝑆𝑖는 𝑥=𝑖에 위치한 사람의 감염상태를 나타내며, 다음과 같다. (1≤𝑖≤𝑁)

• .: 감염되지 않음
• R: 감염됨

 

 

출력

 1일 뒤 Rick-Roll Virus에 감염된 사람들을 𝑀개의 치료제로 모두 치료할 수 있으면 Yes, 아니면 No를 출력한다.

 

 

 

통과한 답안

namespace _29732
{
    internal class Program
    {
        static void Main(string[] args)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int N = int.Parse(inputs[0]);
            int M = int.Parse(inputs[1]);
            int K = int.Parse(inputs[2]);
            string input = Console.ReadLine();
            char[] virus = new char[N];
            for (int i = 0; i < input.Length; i++)
            {
                virus[i] = input[i];
            }

            char[] nextDayVirus = new char[N];
            Array.Copy(virus, nextDayVirus, N);

            for (int i = 0; i < N; i++)
            {
                if (virus[i] == 'R')
                {
                    int start = Math.Max(0, i - K);
                    int end = Math.Min(N - 1, i + K);
                    for (int j = start; j <= end; j++)
                    {
                        nextDayVirus[j] = 'R';
                    }
                }
            }

            int virusCnt = 0;
            foreach (char c in nextDayVirus)
            {
                if (c == 'R')
                    virusCnt++;
            }

            Console.WriteLine(virusCnt > M ? "No" : "Yes");
        }
    }
}

 

1열로 인접해있는 사람들 중에서 1명이 감염되면 1일 후에

일정 범위의 사람들이 감염되는 바이러스가 퍼진 경우,

다음날 감염자의 수가 치료제의 수보다 많은지를 판단하는 문제이다.

 

이 문제를 푸는데 가장 큰 부분이라고 할 수 있는 점은 배열을 2개 사용한다는 것인데,

현재 감염자와 다음날 감염자를 동일한 배열을 사용하지 않기 위해서이다.

현재 감염자가 있는 배열을 순회하면서 다음날 감염될 것으로 예상되는 사람들을

다음날 감염자 배열에서 'R'로 바꿔주는 것이 포인트이다.

 

이후에 다음날 감염자 배열을 순회하면서 감염자의 수를 확인하고

이를 치료제와 비교하는 것으로 해결할 수 있다.

 

감염자가 전염시키는 부분이 배열이 아니라 숫자로 표현했기 때문에

max(0, i - K), min(N - 1, i + K)로 변환해야 되는 부분도 중요했다.