Codeforces Round #762 (Div. 3) A부터 C까지 업솔빙

Codeforces Round #762 (Div. 3) A부터 C까지 업솔빙

나는 개똥벌래~ 코딩을 못하네 알고리즘 못하네~ *1200도 못푸네

A. Square String? (*800)

접기/펼치기

문제 설명
어떤 문자열이 한줄에 두번 연속으로 써있으면 그 문자열을 square 이라고 한다.

문자열 $s$가 주어질때 그 문자열이 square인지 확인하라.

문제 해설
문자열이 2번 연속으로 써있는 것을 확인하기 위해서는 처음부터 문자열의 절반까지 부분 문자열이 절반부터 맨 끝까지 부분 문자열과 같아야 한다. substr() 함수를 쓰면 가볍게 해결

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        string s; cin >> s;
        cout << (s.substr(0, s.size() / 2) == s.substr(s.size() / 2, s.size()) ? "YES" : "NO") << "\n";
    }
    return 0;
}

B. Squares and Cubes (*800)

접기/펼치기

문제 설명
수아는 양의 제곱수와 양의 세제곱수를 좋아한다.

숫자 $n$이 주어질때 $1$ 부터 $n$까지 수 중에서 수아가 좋아하는 숫자의 개수를 구하라.

문제 해설
set을 사용해서 $n$이전까지 제곱수와 세제곱수를 모두 구해서 insert한다음에 그 set에 있는 원소의 개수를 세면 됀다.

정답 코드

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

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        int n; cin >> n;
        set<int> s;
        for(int i = 1; i * i <= n; i++) s.insert(i * i);
        for(int i = 1; i * i * i <= n; i++) s.insert(i * i * i);
        cout << s.size() << "\n";
    }
    return 0;
}

C. Wrong Addition (*1200)

접기/펼치기

문제 설명
수아는 숫자를 더하는 방법을 배우고 있다. 하지만 아직도 덧셈하는 법을 잘 모르는것 같다. 수아는 숫자 $a$와 $b$를 더할때 다음 알고리즘을 사용한다.

1. 한 숫자가 다른 숫자보다 작으면 작은 숫자앞에 $0$을 추가해서 같은 길이로 만든다.
2. 숫자는 맨 오른쪽에서 왼쪽으로 더해진다.
3. 첫번째 단계에서 $a$의 맨 마지막 자릿수와 $b$의 맨 마지막 자릿수를 더하고 그 결과를 적는다.
4. 각 다음 단계에서 수아는 같은 연산을 같은 자릿수 쌍에대해서 실시하고 결과값을 이미 존재한 문자열의 왼쪽에 그대로 적는다.

두 양의 정수 $a$와 $s$가 주어질때, $a$와 $b$를 더했을 때 $s$가 만들어지게 하는 $b$를 찾아라 혹은 $b$가 존재하지 않다는 것을 확인하라.

문제 해설
문제가 의도하는 것을 다 알았지만 원인 모를 215번째 테스트케이스에서 계속 틀려서 못풀었다. 그런데 내가 계속 기를쓰고 풀려고 했던 문제를 업솔빙 하니까 확실히 실력이 느는게 느껴졌다. 포기하지 말자.

결국 맨 뒤에 자리를 확인해야 하므로 그냥 a와 s를 long long 으로 받고 10을 나눈 몫을 구해서 확인하자. 이때 a의 몫을 x, s의 몫을 y라고 하면 다음 2가지 경우가 있다.

1. $x \le y$ 인 경우 그냥 $y - x$가 $b$의 뒤에 들어갈 수이다.
2. $x > y$인 경우 무조건 $s$의 뒤에서 2번째 자리까지 가져와야 한다. $s$의 뒤에서 2번째 자리까지 가져와서 구한 $y$에 대해서 다음 경우를 생각해야한다.
   • 일단 $x < y$이어야 한다. 뒤에서 2번째 자리까지 가져와도 $x > y$라면 뒤에서 2번째 자리는 $0$이라는 뜻이고 그러면 답을 구할 수 없다. 그리고 가져온 $y$값이 $10$보다 크거나 같고, $18$보다 작거나 같아야 한다. $10$이 나온 이유는 $x = 1, y = 0$인 경우에서 $x = 1, y = 10$으로 바뀐 경우이며, $18$이 나온 이유는 $x = 9, y = 8$인 경우에서 $x = 9, y = 18$으로 바뀐 경우이다. 이 두 값에 만족하지 않는다면 b를 구할 수 없기 때문에 마찬가지로 -1을 출력한다.

모든 결과를 확인하고 나서 추가로 확인해줘야 할 것은 $a$가 모두 사용됐는지 여부이다. $s$는 모두 사용했는데, $a$를 사용안했다면 남아있는 $a$의 숫자에 대응할 $s$가 없다는 뜻이다. 따라서 이 경우에도 $-1$을 출력해야 한다.

정답 코드

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

using ll = long long;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int t; cin >> t;
    while(t--){
        ll a, s; cin >> a >> s;
        string b;
        while(s){
            int x = a % 10, y = s % 10;
            if(x > y){
                s /= 10;
                y += (s % 10) * 10;
                if(x < y && y <= 18) b = (char)(y - x + '0') + b;
                else break;
            }else b = (char)(y - x + '0') + b;
            a /= 10, s /= 10;
        }
        cout << (a == 0 && s == 0 ? stoll(b) : -1) << "\n";
    }
    return 0;
}