C++과 친해지기

5/3. 랜선 자르기 (백준 1654번)

 

https://www.acmicpc.net/problem/1654

 

//C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int k, n;
    cin >> k >> n;

    vector<long long> data(k);
    for (int i = 0; i < k; i++) {
        cin >> data[i];
    }

    long long l = 0;
    long long r = data[0] + 1;

    while (l < r) {
        long long m = (l + r) / 2;
        int cnt = 0;
        for (int i = 0; i < k; i++) {
            cnt += data[i] / m;
        }
        if (cnt >= n)
            l = m + 1;
        else if (cnt < n)
            r = m;
    }

    cout << l - 1 << '\n';

    return 0;
}

전형적인 매개변수탐색 문제인 것 같다. 일반적으로 l은 inclusive하게, r은 exclusive하게 잡는다고 한다. 그리고 이렇게 잡으면 구한 값이 key 값보다 크면 l = m + 1로, 작으면 r = m로 바꾼다. 우여곡절 끝에 다 맞게 한 것 같...았는데... 계속 틀렸습니다가 나오네..?? (오답) 왜 그런가 했더니 랜선의 길이가 2^31-1보다 작거나 같으니까 int를 사용하면 오버플로우가 날 수 있는 것이었다. 계속 파이썬을 썼더니 자료형 신경을 안 쓰게 되었다. 이제 잘 신경써야지.. (정답)

 

---

 

5/4. 마인크래프트 (백준 18111번)

 

https://www.acmicpc.net/problem/18111

 

//C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m, b;
    cin >> n >> m >> b;

    vector<vector<int>> data(n, vector<int>(m));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> data[i][j];
        }
    }

    int mint = 1e9, minh, tmp, lack, over;

    for (int h = 0; h <= 256; h++) {
        lack = over = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (data[i][j] > h)
                    over += data[i][j] - h;
                else
                    lack += h - data[i][j];
            }
        }
        if (lack <= over + b) {
            tmp = over * 2 + lack;
            if (tmp <= mint) {
                mint = tmp;
                minh = h;
            }
        }
    }

    cout << mint << ' ' << minh << '\n';
}

그냥.. 브루트포스 구현 문제. (정답)

 

---

 

5/4. 나는야 포켓몬 마스터 이다솜 (백준 1620번)

 

https://www.acmicpc.net/problem/1620

 

//C++

#include <iostream>
#include <map>
#include <string>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    map<int, string> num;
    map<string, int> name;
    string input;

    for (int i = 1; i <= n; i++) {
        cin >> input;
        num.insert({i, input});
        name.insert({input, i});
    }

    for (int i = 0; i < m; i++) {
        cin >> input;
        if (input[0] >= 48 && input[0] < 58) {
            cout << num[stoi(input)] << '\n';
        }
        else {
            cout << name[input] << '\n';
        }
    }
}

빠른 입출력 문제로 유명하지만 사실 나에게는 C++에서 map을 처음 써본 문제. (정답)

map 선언 : map<int, string> m;

map에 데이터 삽입 : m.insert({12, "Pikachu"});