Murra Blog

BOJ 2845번 파티가 끝나고 난 뒤 문제

사람 수 * 넓이를 구하고 기사에 난 수에서 뺀다.

쉬워서 안올리려고 했는데 5번 입력 받는거를 모르고 사람 수만큼 입력받는 줄 알고 틀렸다.

그래서 올렸다..

2845.cpp

#include <bits/stdc++.h>
using namespace std;
int a[11];
int main() {
    int L, P;
    cin >> L >> P;
    int people = L * P;
    for (int i = 0; i < 5; i++) {
        cin >> a[i];
        a[i] -= people;
        cout << a[i] << ' ';
    }
}

BOJ 2935번 소음 문제

A와 B의 입력이 최대 100자리까지 들어올 수 있어서 string을 이용해서 처리했다.

곱하기일 경우엔 1을 출력하고 A와 B의 0의 개수 합 만큼 0을 출력하면 된다.

더하기일 경우엔 같은 자리면 2 출력후 0의 개수 출력을 한다.

자리수가 다르면 1 출력 후 (0의 개수 차이-1)만큼 0을 출력하고, 1을 다시 출력한 후 작은 0의 개수를 출력하면 된다.

2935.cpp

#include <bits/stdc++.h>
using namespace std;
void print0(int t) {
    for (int i = 0; i < t; i++) {
        cout << "0";
    }
}
int main() {
    string a, b;
    char o;
    cin >> a >> o >> b;
    int a0 = a.size() - 1;
    int b0 = b.size() - 1;
    if (o == '+') {
        if (a0 == b0) {
            cout << "2";
            print0(a0);
        } else {
            cout << "1";
            int big = max(a0, b0);
            int small = min(a0, b0);
            print0(big - small - 1);
            cout << "1";
            print0(small);
        }
    }
    if (o == '*') {
        cout << "1";
        print0(a0 + b0);
    }
}

BOJ 2583번 영역 구하기 문제

DFS, BFS 모두 가능한 문제다. 아마.

큐 넣기가 더 귀찮을거 같아서 DFS로 풀었는데, 나는 더 간단한 코드를 보여주기 위해 더 복잡한 코드를 만드는 거 같다. 그래서 이거 푸는데 시간이 생각보다 많이 걸렸다.

앞으로 간결하고 빠르게 짤 수 있는 코딩을 연습해야겠다.

2583.cpp

#include <bits/stdc++.h>
using namespace std;
bool range[101][101];
bool visited[101][101];
int M, N, K;
void DFS(int y, int x, int &area) {
    visited[y][x] = true;
    area++;

    // -1 0 / +1 0 / 0 -1 / 0 +1
    vector<pair<int, int> > wsad;
    wsad.push_back({-1, 0});
    wsad.push_back({+1, 0});
    wsad.push_back({0, -1});
    wsad.push_back({0, +1});

    for (int i = 0; i < 4; i++) {
        int nextY = y + wsad[i].first;
        int nextX = x + wsad[i].second;
        bool yCheck = (nextY >= 0) && (nextY < M);
        bool xCheck = (nextX >= 0) && (nextX < N);
        if (yCheck && xCheck) {
            if (!range[nextY][nextX] && !visited[nextY][nextX])
                DFS(nextY, nextX, area);
        }
    }
}

int main() {
    vector<int> area;
    cin >> M >> N >> K;
    while (K--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        for (int i = y1; i < y2; i++) {
            for (int j = x1; j < x2; j++) {
                range[i][j] = true;
            }
        }
    }
    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            // 네모 영역이 아니면서 방문하지 않은 곳
            if (!range[i][j] && !visited[i][j]) {
                int ar = 0;
                DFS(i, j, ar);
                area.push_back(ar);
            }
        }
    }
    sort(area.begin(), area.end());
    cout << area.size() << '\n';
    for (auto i : area) {
        cout << i << " ";
    }
}

BOJ 1697번 숨바꼭질 문제

BFS 돌다리 문제랑 거의 같다.

-1, +1, 2*현재 자리로 움직일 수 있다.

인덱스 체크가 필요하다.

1697.cpp

#include <bits/stdc++.h>
using namespace std;
int N, K;
bool visited[100001];
int main() {
    cin >> N >> K;

    queue<pair<int, int> > q;
    visited[N] = true;
    q.push({N, 0});
    while (!q.empty()) {
        int position = q.front().first;
        int count = q.front().second;
        q.pop();

        if (position == K) {
            cout << count;
            return 0;
        }
        if (position - 1 >= 0 && !visited[position - 1]) {
            visited[position - 1] = true;
            q.push({position - 1, count + 1});
        }
        if (position + 1 <= 100000 && !visited[position + 1]) {
            visited[position + 1] = true;
            q.push({position + 1, count + 1});
        }
        if (position * 2 <= 100000 && !visited[position * 2]) {
            visited[position * 2] = true;
            q.push({position * 2, count + 1});
        }
    }
}

BOJ 2331번 반복수열 문제

이 문제는 DFS로 풀었다.

각 자리 숫자를 P 제곱한 후 더한게 다음 숫자가 되는 방식인데, 중간에 계속해서 반복되는 구간이 나타난다.

그 구간에 포함되지 않는 숫자들의 갯수를 구하는 문제이다.

자꾸 pow(5, 2)를 24로 출력해서 뭐가 잘못됐나 했는데 pow() 함수의 return type이 실수형이었다.

그래서 반올림해서 정수형으로 변환했다.

2331.cpp

#include <bits/stdc++.h>
using namespace std;
int result;
int visitCount[1000000];

int mult(int A, int P) {
    int next = 0;
    while (A > 0) {
        next += (int)floor(pow(A % 10, P)+0.5);
        A /= 10;
    }
    return next;
}

void DFS(int A, int P) {
    visitCount[A]++;
    if (visitCount[A] > 2) {
        return;
    }
    DFS(mult(A, P), P);
}

int main() {
    int A, P;
    cin >> A >> P;
    DFS(A, P);

    for (int i = 0; i < 100000; i++) {
        if (visitCount[i] == 1) {
            result++;
        }
    }

    cout << result;
}

BOJ 12761번 돌다리 문제

BFS로 풀었다.

8가지 경우가 -1, +1, -skyA, +skyA, -skyB, +skyB, 현재 자리 * skyA, 현재 자리 * skyB이다.

문제에 나와있듯이 100,000보다 크거나 0보다 작은 번호 체크를 해줘야 한다.

12761.cpp

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

bool visited[100001];
queue<pair<int, int> > q;
int main() {
    int skyA, skyB, N, M;
    cin >> skyA >> skyB >> N >> M;

    // BFS Start
    visited[N] = true;
    q.push({N, 0});  // N번자리 0번 만에 왔다
    while (!q.empty()) {
        int position = q.front().first;
        int count = q.front().second;
        q.pop();

        if (position == M) {
            cout << count << '\n';
            return 0;
        }
        int check[8] = {position - 1,
                        position + 1,
                        position - skyA,
                        position + skyA,
                        position - skyB,
                        position + skyB,
                        position * skyA,
                        position * skyB};

        for (int i = 0; i < 8; i++) {
            if (check[i] >= 0 && check[i] <= 100000) {
                if (!visited[check[i]]) {
                    visited[check[i]] = true;
                    q.push({check[i], count + 1});
                }
            }
        }
    }
}

BOJ 16360번 Go Latin 문제

이번 ICPC 본선 문제 중에 유일하게 푼 문제이다. 내가 푼게 아니라서 집에 와서 풀어봤다.

if문으로 각 조건을 비교하고 테이블에 맞게 붙여주거나 수정 후 붙여주면 된다.

테이블에 속하지 않으면 us를 붙인다.

16360.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    while (n--) {
        string s;
        cin >> s;
        int sSize = s.size();

        if (s[sSize - 1] == 'a') {
            s += "s";
        } else if (s[sSize - 1] == 'i' || s[sSize - 1] == 'y') {
            s[sSize - 1] = 'i';
            s += "os";
        } else if (s[sSize - 1] == 'l') {
            s += "es";
        } else if (s[sSize - 1] == 'n') {
            s[sSize - 1] = 'a';
            s += "nes";
        } else if (s[sSize - 1] == 'e' && s[sSize - 2] == 'n') {
            s[sSize - 2] = 'a';
            s[sSize - 1] = 'n';
            s += "es";
        } else if (s[sSize - 1] == 'o') {
            s += 's';
        } else if (s[sSize - 1] == 'r') {
            s += "es";
        } else if (s[sSize - 1] == 't') {
            s += "as";
        } else if (s[sSize - 1] == 'u') {
            s += "s";
        } else if (s[sSize - 1] == 'v') {
            s += "es";
        } else if (s[sSize - 1] == 'w') {
            s += "as";
        } else {
            s += "us";
        }
        cout << s << '\n';
    }
}