2022 SFPC pretest

 

첫날이라 정신도 없고, 서버도 말썽을 많이 부려서 테스트하기 많이 힘들었다. 서버 계속 터져서 중간에 때려 칠려고 한건 비밀~

 

그래도? 결과가 잘 나와서 기분 좋게 집에 갈 수 있었다.

 

문제 분석

0과 1은 세트 문제라서 1풀면 0은 그냥 돌려서 풀 수 있는 단순 출력문제로 나왔다.

 

 

 

A1.

 

테스트 문제라 그런지 A1번은 대회 안내할 때, 문제 예제로 나왔던 문제가 그대로 나왔다.

2일 동안 주차된 위치가 주어지고, 한번도 주차되지 않았거나 2일 연속으로 주차된 공간의 수를 출력하는 문제이다.

 

1차원 배열에 체크하면서 0인 것과 2인 것의 수를 세서 출력하면 된다.

 

#include <iostream>
 
using namespace std;
 
int n, a, b, t, memo[110], ta, tb;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  cin >> n >> a >> b;
  for(int i=0; i<a; i++) {
    cin >> t;
    memo[t]++;
  }
 
  for(int i=0; i<b; i++) {
    cin >> t;
    memo[t]++;
  }
 
  for(int i=1; i<=n; i++) {
    if(memo[i] == 0) ta++;
    if(memo[i] == 2) tb++;
  }
 
  cout << ta << " " << tb << "\n";
 
  return 0;
}
 

 

 

 

B1.

 

각각 10kg, 5kg, 3kg, 1kg 를 담을 수 있는 상자가 있다.

이때, 필요한 상자의 최소 필요 갯수를 구하는 문제이다.

 

그리디로 큰 상자부터 처리하면서 필요한 갯수를 찾으면 되는 문제이다.

O(4)에 해결할 수 있는 매우 쉬운 문제이다.

 

#include <iostream>
 
using namespace std;
 
int n, d[] = {10, 5, 3, 1}, result;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  cin >> n;
  for(int i=0; i<4; i++) {
    result += n/d[i];
    n %= d[i];
  }
 
  cout << result << "\n";
 
  return 0;
}
 

 

 

 

C1.

 

질의 n개와 k가 입력되는데,

n개의 질의가 k를 넘지 않는 한에서의 질의 m의 약수와 배수가 되는 자연수 중, k 이하인 것의 수를 구하는 문제이다.

k = 10^(8~12) 정도 됬었던거 같은데... 잘 기억은 나지 않는다.

 

제일 시간을 오래 쓴 문제이다. 시간 제한이 20초긴 한데... 그래도? O(n)에 돌리면 시간 초과 나올게 뻔해서

연산을 최대한 줄여보려고 노력하였다.

 

처음에는 약수를 다 구하고, 배수도 다 구해서 중복되는 건 조건으로 처리해 날려버리는 식으로 풀었는데, 당연히 시간 초과가 났다.

그런 다음 연산량을 줄여 나가는데,

 

약수를 다 구하지 않고 제곱이 m보다 작거나 같은 경우까지 돌리면서 m/i의 경우와 i의 경우를 모두 set에 넣었다.

배수의 경우에는 그냥 다 돌렸다.

 

이렇게 풀면 시간복잡도가 O(n*(sqrt(m)+log m)) 정도 나온다.

 

#include <iostream>
#include <algorithm>
#include <set>
 
using namespace std;
 
int n, m, v;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  cin >> n >> m;
  for(int i=0; i<n; i++) {
    cin >> v;
 
    set<int> S;
    for(int i=1; i*i<=v; i++) {
      if(m >= i && i*i == v) S.insert(i);
      else if(m >= i && v%i == 0) {
        S.insert(i);
        S.insert(v/i);
      }
    }
 
    for(int j=v; j<=m; j+=v) S.insert(j);
 
    cout << S.size() << "\n";
  }
 
  return 0;
}
 

#include <iostream>
#include <cmath>
 
using namespace std;
typedef long long int INT;
 
INT a, b, r, c, d;
double t;
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  cin >> a >> b >> r >> c >> d;
 
  t = sqrt(pow(c-a, 2)+pow(d-b, 2));
  if(t < r) {
    cout << "in\n";
  } else if(t == r) {
    cout << "on\n";
  } else {
    cout << "out\n";
  }
 
  return 0;
}