Codeforces Raif Round 1 (Div. 1 + Div. 2) A~C번 풀이

중간고사가 4일 남았는데 참가했습니다.

대회 중 A~C번을 풀었습니다.

중간고사ㅠㅠㅠㅠㅠ

A번 - Box is Pull

문제

Problem - A - Codeforces

문제 설명

$(x_1, y_1)$의 박스를 $(x_2, y_2)$로 끌고 가려 합니다.

박스와 인접해 있을 때 박스를 끌면 박스는 내가 있던 위치로 이동하고, 나는 박스 반대편으로 한 칸 이동합니다.

박스를 끌지 않고도 한 번에 한 칸씩 움직일 수 있으며, 내 처음 위치는 마음대로 정할 수 있습니다.

이때 박스를 $(x_1, y_1)$에서 $(x_2, y_2)$로 옮기기 위해 필요한 최소 이동 횟수를 구하는 문제입니다.

풀이

만약 출발지와 목적지의 x좌표가 같다면 y좌표의 차이가 이동 횟수가 됩니다.

마찬가지로 y좌표가 같다면 x좌표의 차이만큼 이동하면 됩니다.

x좌표와 y좌표가 모두 다르면 x좌표가 같도록 상자를 이동시킨 후 상자의 위 또는 아래로 이동하기 위해 두 번 이동한 뒤 y좌표를 같게 만들면 됩니다. 따라서 이 경우에는 $abs(x_1 - x_2) + abs(y_1 - y_2) + 2$가 총 이동 횟수입니다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
void solve() {
    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    int ans = abs(x1 - x2) + abs(y1 - y2);
    if (x1 != x2 and y1 != y2)
        ans += 2;
    cout << ans << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

 

B번 - Belted Rooms

문제

Problem - B - Codeforces

문제 설명

N개의 방이 N개의 벨트를 통해 원형으로 연결되어 있습니다. 0번 벨트는 0, 1번 방을, 1번 벨트는 1, 2번 방을, N-1번 벨트는 N-1, 0번 방을 연결합니다. 벨트는 시계방향으로만 움직이는 벨트, 반시계방향으로만 움직이는 벨트, 양방향 모두 움직이는 벨트 세 종류가 있습니다. 이때 벨트를 타고 나갔다 다시 돌아올 수 있는 방의 수를 구하는 문제입니다.

풀이

만약 방과 연결된 두 벨트 중 하나라도 양방향이라면 돌아올 수 있는 방입니다.

두 벨트 모두 양방향이 아닐 때는 전체 벨트를 보아야 합니다.

전체 벨트가 모두 한 방향(시계방향 혹은 반시계방향)이라면 한 바퀴 돌아 처음 방으로 돌아올 수 있습니다.

하지만 방향이 다른 벨트가 하나라도 있으면 돌아오지 못합니다.

벨트를 하나씩 탐색하며 종류별로 세어 주면 답을 구할 수 있습니다.

코드

#include <iostream>
#include <algorithm>
 
using namespace std;
void solve() {
    int n, cw = 0, anti = 0, off = 0;
    bool cc = false, ac = false;
    string belt;
    char bef, nxt;
    cin >> n >> belt;
    for (int i = 0; i < n; i++) {
        nxt = belt[i];
        if (i)
            bef = belt[i - 1];
        else
            bef = belt[n - 1];
        if (bef == '-' || nxt == '-')
            off++;
        else {
            if (bef == '>')
                cw++;
            if (bef == '<')
                anti++;
        }
        if (bef == '>')
            cc = true;
        if (bef == '<')
            ac = true;
    }
    if (cc ^ ac)
        off += max(anti, cw);
    cout << off << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}
 

대회 중 짠 코드라 좀 더러워요

C번 - ABBB

이 문제 때문에 글을 쓰게 되었습니다.

문제

Problem - C - Codeforces

문제 설명

A와 B로만 이루어진 문자열이 주어질 때, 부분문자열 AB나 BB를 삭제할 수 있습니다. 가능한 AB와 BB를 최대한 삭제했을 때 얻을 수 있는 문자열의 최소 길이를 구하는 문제입니다.

풀이

백준의 PPAP 문제와 거의 같은 문제이며, 그리디 방식으로 풀 수 있습니다.

삭제할 수 있는 AB를 먼저 모두 삭제한 뒤, 삭제할 수 있는 BB를 모두 삭제하면 답을 구할 수 있습니다. 

대회 중에는 연결 리스트를 직접 구현해서 풀었는데, 구현 과정에서 실수를 많이 해서 시간이 오래 걸렸습니다.

대회 중 AC를 받은 코드입니다.

 

다른 사람의 코드를 봤더니 스택을 이용하여 저보다 훨씬 깔끔했습니다.

Editorial에서도 스택을 쓰라고 해서 스택을 이용한 풀이도 작성해 보았습니다.

문자열을 앞에서부터 탐색하며 스택이 비었거나 현재 문자가 A라면 스택에 넣습니다.

스택이 비지 않았고 현재 문자가 B라면 무조건 이전 문자와 현재 문자를 삭제할 수 있으므로 스택의 pop연산을 통해 이전 문자를 삭제합니다.

문자열을 끝까지 탐색한 뒤 스택에 있는 문자의 수가 정답이 됩니다.

코드

#include <iostream>
#include <algorithm>
#include <stack>
 
using namespace std;
void solve() {
    string now;
    cin >> now;
    stack<char> stk;
    for (char i : now) {
        if (stk.empty() or i == 'A')
            stk.push(i);
        else
            stk.pop();
    }
    cout << stk.size() << '\n';
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

 

사족

동아리 수업에서 PPAP 문제를 다뤘는데도 까먹었어요..

수업 열심히 들어야겠다