백준 18429번 : 근손실 (C 언어)

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

18429번: 근손실

Code:

#include <stdio.h>
 
int n, k;
 
int check[9] = { 0, };
int list[9] = { 0, };
int arr[9] = { 0, };
int count = 0;
 
void dfs(int num)
{
    if (num == n)
    {
        int temp = 500;
        int flag = 0;
        for (int i = 0; i < n; i++)
        {
            temp -= k;
            temp += list[i];
            if (temp < 500)
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            count++;
        }
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            if (check[i] == 0)
            {
                list[num] = arr[i];
                check[i] = 1;
                dfs(num + 1);
                check[i] = 0;
            }
        }
    }
}
 
 
int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
    dfs(0);
    printf("%d", count);
}

문제 해결 방법:

이 문제는 N일 동안 N개의 운동 키트를 사용하여 중량을 500 이상으로 유지하는 경우의 수를 찾는 것입니다. 이를 위해 가능한 모든 순열을 생성하고, 각 순열마다 중량을 업데이트하여 중량이 500 이상으로 유지되는지 확인합니다. 여기서 중요한 점은 순열을 생성할 때 각 운동 키트를 사용한 횟수를 계산하고, 각 키트를 한 번만 사용해야 한다는 것입니다.

코드 설명:

1. check, list, arr, count 등의 변수들은 문제 해결을 위해 사용되는 변수입니다.
2. dfs 함수는 재귀적으로 가능한 모든 순열을 생성하고, 각 순열마다 중량을 계산하여 중량이 500 이상인 경우만 count를 증가시킵니다. 이 함수는 현재 순열의 인덱스 num을 기반으로 작동합니다.
3. main 함수에서는 입력으로 N, K, 그리고 각 운동 키트의 중량 증가량을 받습니다.
4. dfs(0)을 호출하여 모든 가능한 순열을 생성하고 count 변수에 항상 중량이 500 이상인 경우의 수를 저장합니다.
5. 마지막으로 count를 출력하여 결과를 표시합니다.