[코드포스 / Codeforces] Round #863 (Div. 3)

Round #863 (Div. 3)

 

 

대회

https://codeforces.com/contest/1811

Dashboard - Codeforces Round 863 (Div. 3) - Codeforces

 

 

푼 문제

A. Insert Digit

정수 n과 d를 입력받아 d를 n의 어딘가에 한 번 적절히 넣어 만들 수 있는 가장 큰 수를 출력하는 문제. 정수 n을 문자열로 받아 앞에서부터 탐색하며 각 자릿수를 x라 하면 d > x인 경우 d를 출력한 다음 x를 출력한다. 이외의 경우(d ≤ x)에는 x만 출력한다. flag를 만들어 d > x인 경우에도 이미 d를 한 번 출력했다면 x만 출력한다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int n, d, flag = 0;
    string s;
    cin >> n >> d >> s;
    for (int i = 0; i < n; i++) {
      int num = s[i] - '0';
      if (num >= d) {
        cout << num;
      } else {
        if (flag) {
          cout << num;
        } else {
          cout << d << num;
          flag = 1;
        }
      }
    }
    if (!flag)
      cout << d;
    cout << '\n';
  }
  return 0;
}

 

 

B. Conveyor Belts

n×n 크기의 배열(n은 2의 배수)에서 양파 껍질처럼 컨베이어 벨트가 설치되어 있다. 각 컨베이어 벨트는 계속해서 움직이고 있고 다른 벨트로 넘어갈 때 1의 에너지가 든다. (x1, y1)에서 (x2, y2)로 가는데 최소 에너지를 구하는 문제다.

 

각 좌표가 몇 번째 벨트에 있는지 구한 다음 차를 출력하면 된다. 따라서 좌표의 가장 바깥으로부터의 최단 거리를 x라 하면 이 좌표는 바깥으로부터 x번째 벨트다. 즉, min(x, y, n - x + 1, n - y + 1)이 번호가 된다. 각각을 a, b라 하면 abs(a-b)가 답이 된다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int n, x1, y1, x2, y2;
    cin >> n >> x1 >> y1 >> x2 >> y2;
    int a = min(min(x1, y1), min(n - x1 + 1, n - y1 + 1));
    int b = min(min(x2, y2), min(n - x2 + 1, n - y2 + 1));
    cout << abs(a - b) << '\n';
  }
  return 0;
}

 

 

C. Restore the Array

배열 a는 배열 b의 인접한 원소 중 큰 원소를 값으로 가지는 배열이다. 즉, 배열 a의 크기는 b의 크기보다 1 작다. 예를 들어 배열 b가 [1, 3, 0, 5, 2, 3]인 경우 a는 [1, 3, 5, 5, 3]가 된다. 이 문제는 a가 주어졌을 때 가능한 b를 출력하는 구성적 문제다. 가장 왼쪽과 오른쪽 칸을 a와 같은 원소로 채우고, 1번 인덱스부터 n-1번 인덱스까지 왼쪽부터 a[i]와 a[i+1]을 비교해 큰 값을 b[i+1]에 채운다.

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int n;
    cin >> n;
    vector<int> a(n - 1), b(n);
    for (int i = 0; i < n - 1; i++)
      cin >> a[i];
    b[0] = a[0];
    b[n - 1] = a[n - 2];
    for (int i = 0; i < n - 2; i++)
      if (a[i] < a[i + 1])
        b[i + 1] = a[i];
      else
        b[i + 1] = a[i + 1];
    for (int i : b)
      cout << i << ' ';
    cout << '\n';
  }
  return 0;
}

 

 

총평 및 여담

열흘만에 참여한 코드포스다. B를 너무 어렵게 생각해서 구현에 시간도 오래 걸리고 TLE도 받았었다. 도망쳐서 바로 C를 풀고 다시 잡았을 때 10분 만에 쉬운 방법이 생각나서 AC 받았다. div3에서 3솔이라 괜찮은 성적이라고 생각하지만 단순하게 생각해서 구현하는 능력 좀 키우고.. 남은 1시간 동안 좀 풀 수 있는 문제가 있었다면.. 싶다.