Softeer [level 3] : 택배 마스터 광우 (C 언어)

https://softeer.ai/practice/info.do?idx=1&eid=581&sw_prbl_sbms_sn=171616 

Softeer

Code:

#include <stdio.h>
#include <limits.h>
 
int min = INT_MAX;
int arr[51] = { 0, };
int check[51] = { 0, };
int num = 0;
 
void swap(int* first, int* second)
{
    int temp = *first;
    *first = *second;
    *second = temp;
}
 
void permutation(int n, int m, int k, int cnt)
{
    if (num == cnt-1) {
        int count = 0;
        int sum = 0;
        int value = 0;
        int index = 1;
        while (1)
        {
            if (count == k)
            {
                break;
            }
            if (value + check[index] <= m)
            {
                value += check[index];
                sum += check[index];
                index++;
            }
            else
            {
                count++;
                value = 0;
            }
            if (index == num+1)
            {
                index = 1;
            }
        }
        if (min > sum)
        {
            min = sum;
        }
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        swap(&arr[i], &arr[n]);
        check[cnt] = arr[n];
        permutation(n - 1, m, k, cnt + 1);
        swap(&arr[i], &arr[n]);
    }
}
 
int main()
{
    int n, m, k;
    scanf("%d %d %d", &n, &m, &k);
    num = n;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &arr[i]);
    }
    permutation(n, m, k, 1);
    printf("%d", min);
}

문제풀이:

1. 모든 경우를 구해야 한다. permutation을 생각해서 순열을 구현하였다.

2. 모든 경우에서 조건에 맞게 설정 후 최소값을 찾았다.

C++ 에서는 next_permutation을 쓰면 된다. <algorithm>라이브러리에 들어가있다.