21W28-구현 - 03 탐욕알고리즘

[moodmine]

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV3FuEG6AMkBBAQ3

[moodmine]

SWEA 1244. 최대 상금

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include <string.h>

char best[7];
int original_change;

void Swap(char* a, char* b)
{
    int temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

int FindBest(char input[], int num_input, int num_change)
{
    int result = 0;
    char temp_input[7];
    int data;
    int k = 0;
    int signal = 0;
    if (num_change == 0)
    {
        return atoi(input);
    }
    else
    {
        for (int i = 0; i < num_input - 1; i++)
        {
            for (int j = i + 1; j < num_input; j++)
            {
                strcpy(temp_input, input);
                Swap(&temp_input[i], &temp_input[j]);
                if (original_change - num_change >= num_input - 2)
                {
                    for (k = 0; k < num_change - 2; k++)
                    {
                        if (temp_input[k] != best[k])
                        {
                            signal = 1;
                            break;
                        }
                    }
                }
                else
                {
                    for (k = 0; k <= original_change - num_change; k++)
                    {
                        if (temp_input[k] != best[k])
                        {
                            signal = 1;
                            break;
                        }
                    }
                }
                if (signal == 1)
                {
                    signal = 0;
                    continue;
                }
                data = FindBest(temp_input, num_input, num_change - 1);
                if (data > result)
                    result = data;
            }
        }
    }
    return result;
}

int main(int argc, char** argv)
{
    int test_case;
    int T;
    //freopen("input.txt", "r", stdin);
    scanf("%d", &T);

    for (test_case = 1; test_case <= T; ++test_case)
    {
        char input[7];
        int num_change;
        scanf("%s %d", &input, &num_change);
        strcpy(best, input);
        original_change = num_change;

        int i = 0, j = 0, k = 0;
        int temp = -1;

        int num_input = 0;
        while (input[i] != '\0')
        {
            num_input++;
            i++;
        }

        for (i = 0; i < num_input; i++)
        {
            temp = best[i];
            for (j = i; j < num_input; j++)
            {
                if (best[j] > temp)
                {
                    temp = best[j];
                    best[j] = best[i];
                    best[i] = temp;
                }
            }
        }

        int result = 0;
        printf("#%d ", test_case);
        result = FindBest(input, num_input, num_change);
        printf("%d\n", result);
    }
    return 0;
}