작성일 :

문제 링크

31881번 - K512에 바이러스 퍼뜨리기

설명

감염 및 치료 쿼리를 처리하며 감염되지 않은 컴퓨터의 수를 시뮬레이션하는 문제입니다.


N개의 컴퓨터가 있는 상태에서, 아래의 세 가지 쿼리가 반복적으로 주어집니다:

  1. 1 x : x번 컴퓨터를 감염시킵니다
  2. 2 x : x번 컴퓨터를 치료합니다
  3. 3 : 감염되지 않은 컴퓨터의 수를 출력합니다


모든 컴퓨터는 처음에 감염되지 않은 상태이며,

이미 감염된 컴퓨터를 다시 감염시키거나 이미 건강한 컴퓨터를 치료하는 경우에는 아무 변화도 없습니다.


접근법

  • N개의 불리언 배열을 만들어 각 컴퓨터의 감염 여부를 관리합니다.
  • 각 쿼리를 처리하면서:
    • 감염시도 시 해당 컴퓨터가 감염되지 않았으면 상태를 변경하고 개수 감소
    • 치료 시 해당 컴퓨터가 감염되었으면 상태를 변경하고 개수 증가
  • 감염되지 않은 컴퓨터 수는 별도로 변수로 유지하여 매 쿼리마다 빠르게 출력합니다.



Code

C#

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using System;
using System.Text;

class Program {
  static void Main() {
    var tokens = Console.ReadLine().Split();
    int n = int.Parse(tokens[0]), q = int.Parse(tokens[1]);

    var infected = new bool[n];
    int free = n;
    var sb = new StringBuilder();

    while (q-- > 0) {
      var input = Console.ReadLine().Split();
      int op = int.Parse(input[0]);

      if (op < 3) {
        int x = int.Parse(input[1]) - 1;

        if (op == 1 && !infected[x]) {
          infected[x] = true;
          free--;
        } else if (op == 2 && infected[x]) {
          infected[x] = false;
          free++;
        }
      } else sb.AppendLine(free.ToString());
    }

    Console.Write(sb.ToString());
  }
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;
typedef vector<bool> vb;

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

  int n, q; cin >> n >> q;
  vb infected(n);
  int free = n;
  while (q--) {
    int op, x; cin >> op;
    if (op < 3) cin >> x, x--;
    if (op == 1 && !infected[x]) infected[x] = true, free--;
    if (op == 2 && infected[x]) infected[x] = false, free++;
    if (op == 3) cout << free << "\n";
  }

  return 0;
}