Murra Blog

BOJ 6359번 만취한 상범 문제

구현을 하다가 잘 안돼서 문제 분류를 보니 다이나믹 프로그래밍이였다.

다이나믹 프로그래밍으로 풀긴 했는데 생각을 해내는게 더 중요한 거 같다.

6359.cpp

#include <bits/stdc++.h>
using namespace std;
bool dp[101];
void solve() {
    memset(dp, 0, sizeof(dp));
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            if (dp[j])
                dp[j] = false;
            else
                dp[j] = true;
        }
    }
    int count = 0;
    for (int i = 1; i <= n; i++) {
        if (dp[i]) count++;
    }
    cout << count << '\n';
}
int main() {
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
}

BOJ 5597번 과제 안 내신 분.. 문제

쉬운 구현 문제이다.

5597.cpp

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

bool check[31];
int main() {
    for (int i = 0; i < 28; i++) {
        int ok;
        cin >> ok;
        check[ok] = true;
    }
    for (int i = 1; i <= 30; i++) {
        if (!check[i]) {
            cout << i << '\n';
        }
    }
}

BOJ 2606번 바이러스 문제

union-find 문제인데, 다 구하고 나서 출력할때 좀 헤맸다.

정렬된 입력이 아니어서 정렬 후 union을 시작한다.

2606.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXX 101
int parent[MAXX], n, conn;

void _union(int, int);
int _find(int);
vector<pair<int, int> > edgeV;
int main() {
    cin >> n >> conn;
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    for (int i = 0; i < conn; i++) {
        int first, second;
        cin >> first >> second;
        edgeV.push_back({first, second});
    }
    sort(edgeV.begin(), edgeV.end());
    for (int i = 0; i < conn; i++) {
        int first = edgeV[i].first;
        int second = edgeV[i].second;
        _union(first, second);
    }
    int test = 1;
    int count = 0;
    for (int i = 2; i <= n; i++) {
        if (_find(1) == _find(i))
            count++;
    }
    cout << count;
}

void _union(int f, int s) {
    int firstParent = _find(f);
    int secondParent = _find(s);
    if (firstParent > secondParent)
        parent[firstParent] = secondParent;
    else
        parent[secondParent] = firstParent;
}

int _find(int i) {
    if (parent[i] == i) {
        return i;
    }
    return parent[i] = _find(parent[i]);
}

BOJ 2566번 최댓값 문제

81번 탐색을 하고 최댓값일때 index를 기억해두면 된다.

2566.cpp

#include <bits/stdc++.h>
using namespace std;
int maxNum, input, index_;
int main() {
    for (int i = 0; i < 81; i++) {
        cin >> input;
        if (maxNum <= input) {
            maxNum = input;
            index_ = i;
        }
    }
    cout << maxNum << '\n';
    cout << index_ / 9 + 1 << ' ' << index_ % 9 + 1;
}

BOJ 2523번 별 찍기 - 13 문제

문제 설명대로 잘 유추하면 풀 수 있다.

2523.cpp

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

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            cout << "*";
        }
        cout << '\n';
    }
    for (int i = n - 1; i > 0; i--) {
        for (int j = 0; j < i; j++) {
            cout << "*";
        }
        cout << '\n';
    }
}

BOJ 1927번 최소 힙 문제

priority queue를 쓰는 간단한 기초 문제였다.

생성할 때만 greater를 넣어서 최소힙으로 만들면 된다.

1927.cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    priority_queue<int, vector<int>, greater<int> > pq;
    int n;
    cin >> n;
    while (n--) {
        int input;
        cin >> input;
        if (input != 0) {
            pq.push(input);
        } else {
            if (pq.empty()) {
                cout << "0" << '\n';
            } else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
    }
}

BOJ 1717번 집합의 표현 문제

0일땐 합집합을 하고, 1일땐 같은 집합인지 확인하는 문제이다.

union-find 기본 문제였다.

1717.cpp

#include <bits/stdc++.h>
using namespace std;
#define MAXX 1000001
int parent[MAXX], n, m, check, first, second;

void _union(int, int);
int find(int);

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    // 일단 자기 자신으로 초기화
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
    }
    while (m--) {
        cin >> check >> first >> second;
        if (!check) {
            _union(first, second);
        } else {
            if (find(first) == find(second)) {
                printf("YES\n");
            } else {
                printf("NO\n");
            }
        }
    }
}

void _union(int f, int s) {
    int firstParent = find(f);
    int secondParent = find(s);
    if (firstParent != secondParent)
        parent[firstParent] = secondParent;
}
int find(int i) {
    if (parent[i] == i) {
        return i;
    } else {
        return parent[i] = find(parent[i]);
    }
}