AtCoder Beginner Contest 187

AtCoder Beginner Contest 187

AtCoder Beginner Contest 187

 

AtCoder Beginner Contest 187에 대한 해설이다.

 

 * 이 글은 code-review 항목의 포스트입니다. code-review 항목에 대해 자세히 알아보고 싶다면, 클릭!

 * 문항 원문은 아래 주소에서 확인 가능합니다. AtCoder Beginner Contest 187

 - atcoder.jp/contests/abc187 [ 바로 가기 ]

 

[2021.01.10] 초판 발행

 

 AtCoder Beginner Contest 187를 사후에 풀이를 한 것을 정리해서 업로드합니다.

 

[A번] Large Digits

 

[문제 및 풀이]

 

 주어진 두 세 자리수의 각 자리수의 합을 구한 후에, 큰 것을 구하는 문제이다.

 

[구현]

 

 주어진 수를 $10$으로 나눈 나머지를 더하고, 그 수를 $10$으로 나누어 가는 식으로 구현하면 된다.

 

[예시 답안]

 

#include <stdio.h>
 
int A, B, Ac, Bc;
 
int main() {
    scanf("%d%d", &A, &B);
 
    while (A) Ac += A % 10, A /= 10;
    while (B) Bc += B % 10, B /= 10;
 
    printf("%d", (Ac > Bc) ? Ac : Bc);
 
    return 0;
}
 

 

[B번] Gentle Pairs

 

[문제 및 풀이]

 

 $x$ 좌표가 다른 $N$개의 점이 주어졌을 때, 그 중에서 다음을 만족하는 서로 다른 두 점의 순서쌍을 구하는 문제다.

 

"두 점을 잇는 직선의 기울기가 $1$ 이상, $-1$ 이하이다."

 

[구현]

 

 $N$이 작기 때문에, 모든 순서쌍을 검토하면 된다. 하지만 기울기를 구할 때, 나눗셈을 하기보다 곱셈을 바꾸어서 나눗셈으로 인한 문제를 미연에 방지하였다.

 

 <유의 사항>

 

 1) 곱셈도 수의 범위를 넘어 설 수 있다. 계산 결과가 항상 해당 자료형 범위에 있는 수에 있는지 확인해야 한다.

 

 2) 곱셈을 바꿀 때, 이항하는 항의 부호에 따른 부등호의 방향을 반드시 숙지해야 한다.

 

$$ -1 \leq \frac{\Delta y}{\Delta x} \leq 1 $$

 

 위 식에서 $\Delta x$가 양수와 음수인지에 따른 처리를 해줘야 한다. $\Delta x$가 양수이면 $ - \Delta x \leq \Delta y \leq \Delta x$이지만, $\Delta x$가 음수이면 $ - \Delta x \geq \Delta y \geq \Delta x$임을 고려해야 한다.

 

 (모든 수의 $x$ 좌표가 다르기 때문에 $\Delta x = 0$인 경우는 주어지지 않는다.)

 

[예시 답안]

 

#include <stdio.h>
 
int N, Ans;
int d[1500][2];
 
int main() {
    int i, u;
 
    scanf("%d", &N);
    for (i = 0; i < N; i++) scanf("%d%d", &d[i][0], &d[i][1]);
 
    for (i = 0; i < N; i++) {
        for (u = i + 1; u < N; u++) {
            if (d[i][0] - d[u][0] < 0 && (d[i][0] - d[u][0] <= d[u][1] - d[i][1]) && (d[u][1] - d[i][1] <= d[u][0] - d[i][0])) Ans++;
            if (d[i][0] - d[u][0] > 0 && (d[i][0] - d[u][0] >= d[u][1] - d[i][1]) && (d[u][1] - d[i][1] >= d[u][0] - d[i][0])) Ans++;
        }
    }
 
    printf("%d", Ans);
 
    return 0;
}
 

 

[C번] 1-SAT

 

[문제 및 풀이]

 

 느낌표가 붙은 문자열과 느낌표가 붙지 않은 문자열이 주어진다. 이 때, 느낌표가 붙은 문자열과 느낌표가 붙지 않은 문자열 중에서, 느낌표를 제외한 부분이 동일한 문자열이 존재하는지 판정하는 문제다. 이 때, 만약 존재한다면 그 문자열을 출력하면 된다.

 

[구현]

 

 $N$ 제한이 $2 \times 10^5$이기 때문에 $O( N ^ 2 )$으로 구현하면 최악의 경우에 제한시간 안에 답을 내지 못할 수 있다. 그래서 한 요소를 정렬한 이후에 이분탐색을 하는 방식으로 구현해서, $O ( N ln N )$ 안에 답이 나오도록 구현하였다.

 

 느낌표 유무에 따라서 두 개의 vector 자료구조에 나누어서 보관한다. 이후 vector 하나를 정렬한 후에, 나머지 하나의 원소 하나하나를 정렬한 vector에서 이분검색(lower_bound 함수)을 확인하였다.

 

<유의 사항>

 

 데이터 중에 느낌표가 붙은 것이 아예 안 들어오거나, 느낌표가 안 붙은 것이 아예 안 들어올 수 있다. 이 때, 정렬하는 유형의 문자열이 아예 없는 경우에 문제가 생길 수 있습니다. 즉, vector에 원소를 아예 넣지 않고 어떤 명령을 하는 경우에 runtime error가 나타날 수 있다. 이에 대한 예외 처리를 해야한다.

 

[예시 답안]

 

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
#define Max 250000
 
using namespace std;
 
struct str { char in[20]; };
bool operator < (const str &A, const str &B) { return (strcmp(A.in, B.in) < 0) ? true : false; }
 
int N, L, A, B;
str d[Max];
vector<str> a, b;
 
int main() {
    int i, p;
    str d;
    char in[20];
 
    scanf("%d", &N);
 
    while (N--) {
        scanf("%s", in);
        L = strlen(in);
 
        if (in[0] == '!') {
            for (i = 1; i < L; i++) d.in[i - 1] = in[i];
            d.in[i - 1] = 0, a.push_back(d);
        }
 
        else {
            for (i = 0; i < L; i++) d.in[i] = in[i];
            d.in[i] = 0, b.push_back(d);
        }
    }
 
    A = a.size(), B = b.size();
    sort(b.begin(), b.end());
 
    if (B) {
        for (i = 0; i < A; i++) {
            p = lower_bound(b.begin(), b.end(), a[i]) - b.begin();
            if (strcmp(a[i].in, b[p].in) == 0) break;
        }
    }
    else i = A;
 
    printf("%s", (i == A) ? "satisfiable" : a[i].in);
 
    return 0;
}
 

 

[D번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[E번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]

 

 

 

[F번] (작성 전)

 

[문제 및 풀이]

 

[구현]

 

[예시 답안]