c c++ 언어 공부

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

Code C 2023. 9. 14. 12:28

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

 

18429번: 근손실

웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로

www.acmicpc.net

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#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);
}
 cs

문제 해결 방법:

이 문제는 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를 출력하여 결과를 표시합니다.