[그리디] 큰 수의 법칙

문제

주어진 수를 규칙에 따라 M번 더하여 가장 큰 수를 만든다.

---

내 풀이

• 가장 큰 수와 두번째로 큰 수만 저장
• count == m 까지 규칙대로 더한다.

#pragma warning(disable: 4996)

#include <stdio.h>

int main()
{
    int n, m, k, sum = 0;
    int arr[1000] = {};

    //n m k 입력받기
    scanf("%d %d %d",&n, &m, &k);
    // n개의 자연수 입력받기
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    // 내림차순 정렬
    for (int j = 0; j < n; j++)
    {
        for (int i = j+1; i < n; i++)
        {
            int temp = 0;
            if (arr[j] < arr[i])
            {
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }

    // m번동안 반복
    int count = 0;
    while(count < m)
    {
        for (int j = 0; j < k; j++)
        {
            sum += arr[0];
            count++;

            if (count == m)
                break;
        }
        sum += arr[1];
        count++;
    }

    printf("%d", sum);
}

 

교재 풀이

https://github.com/ndb796/python-for-coding-test/blob/master/3/2.cpp

• vector 자료형 사용, sort()로 정렬
• 가장 큰 수와 두번째로 큰 수 따로 저장 (동일)
• 가장 큰 수가 더해지는 횟수를 계산하여 연산

#include <bits/stdc++.h>

using namespace std;

int n, m, k;
vector<int> v;

int main() {
    // N, M, K를 공백을 기준으로 구분하여 입력 받기
    cin >> n >> m >> k;

    // N개의 수를 공백을 기준으로 구분하여 입력 받기
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        v.push_back(x);
    }

    sort(v.begin(), v.end()); // 입력 받은 수들 정렬하기
    int first = v[n - 1]; // 가장 큰 수
    int second = v[n - 2]; // 두 번째로 큰 수

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

    int result = 0;
    result += cnt * first; // 가장 큰 수 더하기
    result += (m - cnt) * second; // 두 번째로 큰 수 더하기

    cout << result << '\n'; // 최종 답안 출력
}

 

리뷰

vector 자료형을 쓰도록 해야겠다.

배열을 최대 경우까지 생각해서 선언하려니까 정렬할 때도 범위도 그렇고 신경쓰이는게 많았다.