[이취코] 1. 그리디(탐욕법) - C++

1. 그리디(Greedy)란 '탐욕'이란 의미

즉, 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

[예제 1] 거스름돈

5585번: 거스름돈

접근 방향 👉 가장 큰 화폐 단위부터 거슬러 주는 것

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

vector<int> v = {500, 100, 50, 10, 5, 1};

int solution(int n) {
    int cnt = 0;
    int remaining = 1000 - n;

    for (int i = 0; i < v.size() && remaining > 0; i++) {
        cnt += remaining / v[i];
        remaining %= v[i];
    }
    return cnt;
}

int main() {
    int n;
    cin >> n;
    cout << solution(n);
    return 0;
}

 

 

[실전 1] 큰 수의 법칙

✔️ 문제
'큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 방법이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다.

예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때, M이 8이고 K가 3이라고 가정하자.
이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.

예를 들어 순서대로 3, 4, 3, 4, 3으로 이루어진 배열이 있을 때 M이 7이고 K가 2라고 가정하자. 이 경우 두 번째 원소에 해당하는 4와 네 번째 원소에 해당하는 4를 번갈아 두 번씩 더하는 것이 가능하다.
결과적으로 4 + 4 + 4 + 4 + 4 + 4 + 4 인 28이 도출된다.

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

 

✔️  입력

• 첫째 줄에 N(2 <= N <= 1000), M(1 <= M <= 10000), K(1 <= K <= 10000)의 자연수가 주어지며 각 자연수는 공백으로 구분한다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분한다. 단, 각각의 자연수는 1 이상 10000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

✔️  출력

• 첫째 줄에 동빈이의 큰수의 법칙에 따라 더해진 답을 출력한다.

접근 방향 👉 정렬 + Cnt와 K 비교

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

vector<int> v;

int solution(int n, int m, int k) { //M번 더하기, K번 초과해 더해질 수 없음
    int result = 0, cnt = 0;
    sort(v.begin(), v.end(), greater<>());

    for (int i = 0; i < m; i++) {
        if (cnt >= k) {
            result += v[1];
            cnt = 0;
        } else {
            result += v[0];
            cnt++;
        }
    }

    return result;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    cout << solution(n, m, k);
    return 0;
}

---

📍 간단하게 푸는 방법
반복되는 수열에 대해서 파악하기

 

첫 번째 예에서 6 + 6 + 6 + 5 가 반복된다. 반복되는 수열의 길이는? K+1인 4인 것이다.

따라서 M을 (K+1)로 나눈 몫이 수열이 반복되는 횟수가 된다.

BUT! M이 (K+1)로 나누어 떨어지지 않는 경우도 고려애햐함 => 나머지 !

int(M/(K+1))*K + M%(K+1)

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

vector<int> v;

int solution(int n, int m, int k) { //M번 더하기, K번 초과해 더해질 수 없음
    int result = 0;
    sort(v.begin(), v.end(), greater<>());

    //가장 큰 수가 더해지는 횟수 계산하기
    int cnt = (m / (k + 1)) * k;
    cnt += m % (k + 1);

    result += cnt * v[0];
    result += (m - cnt) * v[1];
    
    return result;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    v.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    cout << solution(n, m, k);
    return 0;
}

 

[실전 2] 숫자 카드 게임

✔️ 문제
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

카드들이 N x M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

 

✔️  입력

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 <= N, M <= 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

✔️  출력

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

접근 방향 👉  정렬 후 행에서 최솟값이 제일 큰 수 찾기

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

vector<vector<int>> v;

int main() {
    int n, m, result = 0;
    cin >> n >> m;
    v.resize(n);
    for (int i = 0; i < n; i++) {
        v[i].resize(m);
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> v[i][j];
        }
        sort(v[i].begin(), v[i].end());
    }
    for (int i = 0; i < n; i++) {
        if (result < v[i][0]) {
            result = v[i][0];
        }
    }

    cout << result;
    return 0;
}

[실전 3] 1이 될 때까지

✔️ 문제
어떠한 수 N이 1이 될 때 까지 다음의 두 과정 중 하나를 반복적으로 선택해 수행하려 함

단, 두번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있음

1. N에서 1을 뺀다.
2. N을 K로 나눈다.

N이 1이 될 때 까지 1번 혹은 2번의 과정을 수행해야하는 최소 횟수를 구하는 프로그램을 작성

 

✔️  입력

• 첫째 줄에 N(2<= N <= 100000)과 K(2 <= K <= 100000)가 공백으로 구분되며 각각 자연수로 주어짐
• 이때, 입력으로 주어지는 N은 항상 K보다 크거나 같음

✔️  출력

• 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력

접근 방향 👉  1 아니면 k나누던가 1빼기

#include <iostream>
using namespace std;

int main() {
    int n, k, cnt = 0;
    cin >> n >> k;

    while (n != 1) {
        if (n % k == 0) {
            n /= k;
        } else {
            n -= 1;
        }
        cnt++;
    }

    cout << cnt;

    return 0;
}

📍 N이 100억 이상 큰 수가 되는 경우, 빠르게 동작하려면

N이 K의 배수가 되도록 효율적으로 한번에 빼는 방식

#include <iostream>
using namespace std;

int main() {
    int n, k, result = 0;
    cin >> n >> k;

    while (true) {
        //N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
        int target = (n / k) * k; //n이 k로 나누어 떨어지지 않을 때 가장 가까운 k로 나누어 떨어지는 수 찾기
        result += n - target; //1을 빼야하는 cnt 더하기
        n = target;

        //cout << "n: " << n << ", result: " << result << endl;
        
        // N이 K보다 작을 때 (더 이상 나눌 수 없을 때) 반복문 탈출
        if (n < k)
            break;
        result += 1; //나눌 때
        n /= k;
    }
    //마지막으로 남은 수에 대하여 1 빼기
    result += n - 1;
    cout << result;

    return 0;
}