[백준 18856] 피드백 (C#, C++) - soo:bak

문제 링크

18856번 - 피드백

설명

문제의 조건에 맞는 수열을 생성하는 문제입니다.

생성해야 하는 수열의 조건들은 다음과 같습니다.

• 수열의 크기는 n 입니다.
  
• 수열의 각 항은 이전 항보다 커야 합니다.
  
• 수열의 각 항은 1 과 1,000 사이의 정수 입니다.
  
• 수열의 두 번째 항은 반드시 2 입니다.
  
• 수열의 마지막 항은 반드시 소수 여야 합니다.
  

입력받은 n 에 대하여, 수열의 두 번째 항이 2 이므로, 조건에 따라서 첫 번째 항은 반드시 1 이 될 것입니다.

이후, 세 번째 항부터 n - 1 번째 항 까지는, 단순히 이전 항 보다 큰 아무 수를 선택할 수 있습니다.

다만, 선택 가능한 수의 범위는 3 부터 1,000 까지 입니다.

마지막으로, n 번째 항은 n - 1 번째 항의 수보다 큰 소수를 선택하면 됩니다.

소수를 구하기 위해서는 에라토스테네스의 체 를 활용하였습니다.

에라토스테네스의 체 에 관련해서는 여기 에서 확인하실 수 있습니다.

---

Code

[ C# ]

namespace Solution {
  class Program {

    static List<int> GeneratePrimeNums(int maxNum) {
      var isPrime = Enumerable.Repeat(true, maxNum + 1).ToArray();
      isPrime[0] = isPrime[1] = false;

      for (int i = 2; i * i <= maxNum; i++) {
        if (isPrime[i]) {
          for (int j = i * i; j <= maxNum; j += i)
            isPrime[j] = false;
        }
      }

      var primes = new List<int>();
      for (int i = 2; i <= maxNum; i++) {
        if (isPrime[i]) primes.Add(i);
      }

      return primes;
    }

    static void Main(string[] args) {

      var n = int.Parse(Console.ReadLine()!);

      var primes = GeneratePrimeNums(1_000);

      Console.WriteLine(n);
      Console.Write("1 2 ");

      int ele = 2;
      for (int i = 3; i < n; i++) {
        ele++;
        Console.Write($"{ele} ");
      }

      foreach (var prime in primes) {
        if (prime > ele) {
          Console.WriteLine(prime);
          break ;
        }
      }

    }
  }
}

[ C++ ]

#include <bits/stdc++.h>

using namespace std;

vector<int> generatePrimeNums(const int& maxNum) {
  vector<bool> isPrime(maxNum + 1, true);
  isPrime[0] = isPrime[1] = false;

  for (int i = 2; i * i <= maxNum; i++) {
    if (isPrime[i]) {
      for (int j = i * i; j <= maxNum; j += i)
        isPrime[j] = false;
    }
  }

  vector<int> primes;
  for (int i = 2; i <= maxNum; i++) {
    if (isPrime[i]) primes.push_back(i);
  }

  return primes;
}

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

  int n; cin >> n;

  vector<int> primes = generatePrimeNums(1'000);

  cout << n << "\n";
  cout << "1 2 ";

  int ele = 2;
  for (int i = 3; i < n; i++) {
    ele++;
    cout << ele << " ";
  }

  for (int prime : primes) {
    if (prime > ele) {
      cout << prime << "\n";
      break ;
    }
  }

  return 0;
}