백준 BOJ 안 푼 문제들 중에서 쉬운 문제들 아무거나 220824

백준 BOJ 1477번 : 휴게소 세우기

문제 난이도 : Gold IV

알고리즘 분류 : 이분 탐색

 

길이가 K인 도로 위에 N개의 휴게소가 있고, 여기에 M개의 휴게소를 더 지어 휴게소 간 거리의 최댓값이 최소가 되도록 할 때, 그 최솟값을 구하는 문제이다.

 

이분 탐색을 이용하여 풀이할 수 있다.

답을 m으로 두고 l ~ r 범위 내에서 이분 탐색을 하면서 휴게소 간의 거리를 m으로 두고 휴게소를 설치했을 때 휴게소가 M개 이하로 설치되었는지 확인하면서 값을 갱신해주면 된다.

 

주의할 점은 두 휴게소 사이의 거리가 x라면, 휴게소는 max(x-1, 0) / m개 설치된다.

왜냐하면, 예를 들어서 생각해보면 휴게소 사이의 거리가 100인데 거리 50으로 휴게소를 설치한다고 하여 휴게소가 2개 설치되지는 않기 때문이다. (0, 50, 100에 위치에 휴게소가 있으면 되므로 1개만 설치하면 된다.)

비슷한 방식으로 거리 101의 도로에 휴게소를 50 간격으로 설치할 때는 2개가 설치되므로, 식을 (x-1) / m으로 두어야 함을 알 수 있다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M, K; cin >> N >> M >> K;

    vector<int> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    v.push_back(0);
    v.push_back(K);

    sort(v.begin(), v.end());

    vector<int> u;
    for(int i=1; i<v.size(); i++) u.push_back(max(v[i]-v[i-1]-1, (int)0));

    int ans = INT_MAX, l = 1, r = K;

    while(l <= r) {
        int m = (l + r) / 2;

        int sum = 0;
        for(int i=0; i<u.size(); i++) sum += u[i] / m;

        if(sum <= M) {
            ans = min(ans, m);

            r = m - 1;
        }
        else l = m + 1;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 4232번 : Conformity

문제 난이도 : Silver IV

알고리즘 분류 : 구현, 해시를 사용한 집합과 맵

 

N개의 5개 숫자의 조합이 주어질 때, 이 조합들 중 가장 빈도가 높은 것의 개수를 구하는 문제이다.

 

map<vector<int>, int>을 이용하여 각 조합의 수를 map에 기록하고 (물론 정렬 후 추가해주어야 한다.) 다시 모든 조합에 대해 map의 값을 확인해보면서 최대인 것의 개수를 count 해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        map<vector<int>, int> m;
        vector<vector<int>> v(N, vector<int>(5));

        for(int i=0; i<N; i++) {
            for(int j=0; j<5; j++) cin >> v[i][j];

            sort(v[i].begin(), v[i].end());

            m[v[i]]++;
        }

        int Max = 0;

        for(int i=0; i<N; i++)
            Max = max(Max, m[v[i]]);

        int ans = 0;

        for(int i=0; i<N; i++)
            if(m[v[i]] == Max) ans++;

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 10489번 : Even Up Solitaire

문제 난이도 : Silver IV

알고리즘 분류 : 스택

 

N개의 수열이 주어질 때, 인접한 두 수의 합이 짝수면 제거할 수 있다고 할 때 남길 수 있는 수의 최소 개수를 구하는 문제이다.

 

stack을 이용하여 수를 하나씩 입력받으면서, 현재 stack의 top에 있는 수와 새로 들어온 수의 합이 짝수면 두 수를 제거해주고, 아니면 그대로 push 해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    stack<int> s;

    while(N--) {
        int x; cin >> x;

        if(!s.empty() && (s.top() + x) % 2 == 0) s.pop();
        else s.push(x);
    }

    cout << s.size() << "\n";
}

 

 

백준 BOJ 14402번 : 야근

문제 난이도 : Silver IV

알고리즘 분류 : 해시를 사용한 집합과 맵

 

하루동안의 출퇴근 기록이 주어지고, 출근은 +, 퇴근은 -일 때 출근 없이 퇴근만 찍히거나 퇴근 없이 출근만 찍혀있는 경우를 야근이라고 할 때, 야근하는 사람의 수를 구하는 문제이다.

 

먼저 입력이 "이름 기호" 순으로 주어지므로, string을 기록할 map이 필요하다.

이제 이 map에 대응되는 int 값을 증감시키면 되는데, 값이 0인데 -가 찍히는 경우와 입력이 끝났는데 남아있는 + 값은 전부 야근에 해당되므로 답에 합해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    unordered_map<string, int> m;
    set<string> s;
    int ans = 0;

    while(N--) {
        string str; cin >> str;
        char c; cin >> c;

        if(c == '+') m[str]++;
        else {
            if(m[str] == 0) ans++;
            else m[str]--;
        }

        if(s.count(str) == 0) s.insert(str);
    }

    for(auto i : s) ans += m[i];

    cout << ans << "\n";
}

 

 

백준 BOJ 10657번 : Cow Jog

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

1차원 좌표 상에서 좌표의 오름차순으로 소의 위치와 오른쪽으로 이동하는 속도가 주어질 때, 두 소가 만나면 추월하지 못하고 같이 이동해야 한다면 최종적으로 소는 몇 그룹으로 묶일지 구하는 문제이다.

 

더 오른쪽에 있는 소가 더 느릴 경우 두 소는 같은 그룹이 되므로, 맨 오른쪽에서 시작하여 최솟값을 가지는 소가 나올 때마다 그 소가 하나의 그룹을 만든다고 생각하면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> v(N);
    for(int i=0; i<N; i++) {
        int x; cin >> x >> v[i];
    }

    int Min = INT_MAX, ans = 0;

    for(int i=N-1; i>=0; i--) {
        if(v[i] <= Min) {
            Min = v[i];
            ans++;
        }
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 6296번 : Crazy Search

문제 난이도 : Silver V

알고리즘 분류 : 해시를 사용한 집합과 맵

 

사용된 문자의 종류가 M인 문자열이 주어질 때, 모든 길이가 N인 부분 수열의 종류를 구하는 문제이다.

 

unordered_map을 사용하여 쉽게 해결이 가능하다.

substr 함수는 꽤 느리게 동작하지만, 이 문제에서는 시간 초과 없이 해결이 가능하다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    string str; cin >> str;

    unordered_map<string, bool> m;
    int ans = 0;

    for(int i=0; i<str.length()-N+1; i++) {
        string tmp = str.substr(i, N);

        if(!m[tmp]) ans++;

        m[tmp] = true;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 19817번 : Company Merging

문제 난이도 : Silver V

알고리즘 분류 : 우선순위 큐

 

두 회사를 합병할 때, 두 회사의 최고 임금의 격차만큼 최고 임금이 적은 기업의 모든 직원에게 추가 급여를 준다고 할 때, N개의 회사를 합병하는 데 필요한 최소 비용을 구하는 문제이다.

 

합병을 처음에 하나 나중에 하나 결국 최대 비용을 가진 사람을 기준으로 비용이 증가하므로, 합병 순서는 관계 없다.

N개 회사 중 최대 급여를 받는 사람의 급여에서 어떤 기업의 최대 급여를 받는 사람의 급여의 격차에 그 회사의 사람 수를 곱한 값들의 합이 답이 된다.

따라서 우선순위 큐를 N개 선언하고, 이들의 최댓값들을 미리 정렬해둔 뒤 답을 쉽게 구할 수 있다.

자세한 구현은 코드를 참고하자.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<priority_queue<int>> pq(N);
    int Max = 0;

    for(int i=0; i<N; i++) {
        int M; cin >> M;

        while(M--) {
            int x; cin >> x;

            pq[i].push(x);

            Max = max(Max, x);
        }
    }

    int ans = 0;

    for(int i=0; i<N; i++)
        ans += (Max - pq[i].top()) * pq[i].size();

    cout << ans << "\n";
}

 

 

백준 BOJ 10689번 : Hamza

문제 난이도 : Silver V

알고리즘 분류 : 해시를 사용한 집합과 맵

 

N개의 수가 주어질 때, 각 번호는 문제의 유형을 나타내고, 문제는 무조건 앞에서부터 푼다고 할 때 모든 유형의 문제를 풀기 위해서는 몇 문제를 풀어야 하는지 구하는 문제이다.

문제의 목록에는 모든 문제의 유형이 포함되어있다는 보장이 있으므로, 새로운 유형이 마지막으로 나온 지점까지가 답이 된다.

따라서 map을 이용하여 번호가 이전에 나온적 있는지의 여부를 기록해주고, 나온 적 없는 번호가 있다면 답을 현재 위치로 갱신해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N; cin >> N;

        unordered_map<int, bool> m;
        int ans = 0;

        for(int i=0; i<N; i++) {
            int x; cin >> x;

            if(!m[x]) ans = i+1;

            m[x] = true;
        }

        cout << "Case " << t << ": " << ans << "\n";
    }
}

 

 

백준 BOJ 1331번 : 나이트 투어

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

주어진 36개의 칸의 목록이 6x6 나이트투어, 즉 체스 나이트가 모든 칸을 경유한 뒤 다시 원래대로 돌아올 수 있는 경로인지를 검사하는 문제이다.

 

검사해야 하는 것은 다음의 세 가지이다.

1. 주어진 칸들 중에서 중복이 없는가 (= 모든 칸을 방문했는가)

2. 인접한 칸들 사이의 격차가 x는 2만큼, y는 1만큼 또는 x는 1만큼, y는 2만큼 나는가

3. 마지막 칸에서 첫 번째 칸으로 이동이 가능한가

 

위의 세 가지를 구현해주면 된다.

자세한 구현은 코드를 참고하자.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<string> str(36);

    for(int i=0; i<36; i++) cin >> str[i];

    bool check = true;

    for(int i=0; i<36; i++) {
        int x = str[i][0] - str[(i+1) % 36][0];
        int y = str[i][1] - str[(i+1) % 36][1];

        if(!((abs(x) == 1 && abs(y) == 2) || (abs(x) == 2 && abs(y) == 1))) check = false;
    }

    for(int i=0; i<36; i++)
        for(int j=i+1; j<36; j++)
            if(str[i] == str[j]) check = false;

    if(check) cout << "Valid\n";
    else cout << "Invalid\n";
}

 

 

백준 BOJ 1417번 : 국회의원 선거

문제 난이도 : Silver V

알고리즘 분류 : 우선순위 큐

 

N명의 후보들의 득표 수가 주어질 때, 1번 후보가 단독 1위를 하기 위해서 다른 후보들의 표에서 매수해와야 하는 사람의 최소 수를 구하는 문제이다.

 

우선 순위 큐를 이용하여 2~N번 후보의 득표 수를 저장하고, 가장 많은 득표를 한 사람의 표를 1개씩 매수해오면서 1등이 언제 되는지 구해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    int cur; cin >> cur;

    priority_queue<int> pq;

    for(int i=0; i<N-1; i++) {
        int x; cin >> x;

        pq.push(x);
    }

    if(N == 1) {
        cout << 0 << "\n";
        return 0;
    }

    int ans = 0;

    while(true) {
        if(cur > pq.top()) break;

        int x = pq.top();
        pq.pop();
        pq.push(x-1);

        cur++;
        ans++;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 4649번 : Tanning Salon

문제 난이도 : Silver V

알고리즘 분류 : 구현

 

N개의 침대가 있는 salon에 문자열로 각 손님의 방문과 떠나는 순서가 주어졌을 때, tanning을 하지 못하고 떠난 손님의 수를 구하는 문제이다.

 

문제에서 tanning을 하지 못한 손님은 반드시 tanning 중인 다른 손님보다 먼저 떠난다고 하였으므로, 매 방문마다 bool 변수가 check 된 것의 개수를 count 해주어 그것이 N보다 큰지 작은지를 파악해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        string str; cin >> str;

        vector<bool> v(26);
        int ans = 0;

        for(int i=0; i<str.length(); i++) {
            int cnt = 0;

            for(int i=0; i<26; i++)
                if(v[i]) cnt++;

            int x = str[i] - 'A';

            if(!v[x]) {
                if(cnt >= N) ans++;

                v[x] = true;
            }
            else v[x] = false;
        }

        if(ans == 0) cout << "All customers tanned successfully.\n";
        else cout << ans << " customer(s) walked away.\n";
    }
}

 

 

백준 BOJ 4675번 : Word Amalgamation

문제 난이도 : Bronze I

알고리즘 분류 : 해시를 사용한 집합과 맵, 트리를 사용한 집합과 맵

 

사전에 있는 단어들의 목록이 주어지고, 그 다음 철자 순서가 섞인 단어들이 주어질 때, 섞인 단어들의 철자를 바꾸어 만들 수 있는 사전의 단어들의 목록을 사전 순으로 출력하는 문제이다.

 

먼저 사전에 있는 단어들을 문자 각각을 정렬을 한 상태로 (ex : apple → aelpp) 해당 문자열과 연결된 set에 원래 단어를 저장한다.

그 다음 순서가 섞인 단어가 입력되면, 이 역시 정렬한 뒤 map에 저장되어 있는지 체크하고, 저장되어 있다면 해당 map과 연결된 set에서 값들을 찾아와 출력해주면 된다.

set은 단어들이 정렬된 상태로 저장되므로, set의 모든 원소들을 출력해주기만 하면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    map<string, set<string>> m;

    while(true) {
        string str; cin >> str;
        if(str == "XXXXXX") break;

        string tmp = str;

        sort(tmp.begin(), tmp.end());

        m[tmp].insert(str);
    }

    while(true) {
        string str; cin >> str;
        if(str == "XXXXXX") break;

        sort(str.begin(), str.end());

        if(m[str].empty()) cout << "NOT A VALID WORD\n";
        else {
            for(auto i : m[str]) cout << i << "\n";
        }

        cout << "******\n";
    }
}

 

 

백준 BOJ 16466번 : 콘서트

문제 난이도 : Bronze I

알고리즘 분류 : 해시를 사용한 집합과 맵

 

N개의 수가 주어질 때, 주어진 수들 중 나타나지 않는 가장 작은 자연수를 구하는 문제이다.

 

map을 이용하여 map에 나온 숫자들을 모두 기록하고, 1부터 확인하면서 map에 없는 최초의 값을 답으로 얻어주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    unordered_map<int, bool> m;

    while(N--) {
        int x; cin >> x;

        m[x] = true;
    }

    for(int i=1; ; i++) {
        if(!m[i]) {
            cout << i << "\n";
            break;
        }
    }
}