21W39-최적화 - 02 동적계획법의 소개

[moodmine]

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

[moodmine]

SWEA 1258. 행렬찾기

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

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)
    {
        printf("#%d ", test_case);
        int n;
        scanf("%d", &n);
        int arr[100][100][2] = { 0, };
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                scanf("%d", &arr[i][j]);
            }
        }

        int sub[20][2] = { 0, };
        int num_sub = 0;
        int k = 0;
        int L = 0;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (!arr[i][j][1] && arr[i][j][0] != 0)
                {
                    k = i;
                    while (arr[k][j][0] != 0)
                    {
                        sub[num_sub][0]++;
                        k++;
                    }
                    k = j;
                    while (arr[i][k][0] != 0)
                    {
                        sub[num_sub][1]++;
                        k++;
                    }

                    for (k = i; k < i + sub[num_sub][0]; k++)
                    {
                        for (L = j; L < j + sub[num_sub][1]; L++)
                        {
                            arr[k][L][1] = 1;
                        }
                    }
                    num_sub++;
                }
            }
        }

        int input[20] = { 0, };
        for (int i = 0; i < num_sub; i++)
        {
            input[i] = sub[i][0] * sub[i][1];
        }
        int temp;
        int temp2;
        int temp3;
        int j;
        for (int i = 0; i < num_sub; i++)
        {
            temp = input[i];
            temp2 = sub[i][0];
            temp3 = sub[i][1];
            j = i - 1;

            while ((j >= 0) && (temp <= input[j]))
            {
                input[j + 1] = input[j];
                sub[j + 1][0] = sub[j][0];
                sub[j + 1][1] = sub[j][1];
                j = j - 1;
            }
            input[j + 1] = temp;
            sub[j + 1][0] = temp2;
            sub[j + 1][1] = temp3;
        }
        printf("%d ", num_sub);
        for (int i = 0; i < num_sub; i++)
        {
            printf("%d %d ", sub[i][0], sub[i][1]);
        }
        printf("\n");
    }
    return 0;
}

[happy-oh]

SW1258

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<string.h>
#include<cmath>
#define MAX_VALUE 10000
using namespace std;

int input_array[100][101];
int array_check[100][100]; //initialize is essential

int mul_answer[20];
int row_answer[20];
int col_answer[20];
int sorting_check[20]; /// need, saved number of answer
int number_of_answer;

void Finding_answer(int n)
{
    int idx, jdx, kdx, mdx;
    for (idx = 0; idx < n; ++idx)
    {
        for (jdx = 0; jdx < n; ++jdx)
        {
            if (array_check[idx][jdx] == 1)
                continue;
            if (input_array[idx][jdx] != 0)
            {
                int row_finish = idx;
                int col_finish = jdx;
                while (input_array[idx][col_finish] != 0)
                {
                    col_finish = col_finish + 1;
                }
                col_answer[number_of_answer] = col_finish - jdx;
                while (input_array[row_finish][jdx] != 0)
                {
                    row_finish = row_finish + 1;
                }
                row_answer[number_of_answer] = row_finish - idx;

                mul_answer[number_of_answer] = (col_finish - jdx) * (row_finish - idx);

                number_of_answer++;

                //check ...
                for (kdx = 0; kdx < row_answer[number_of_answer - 1]; ++kdx)
                {
                    for (mdx = 0; mdx < col_answer[number_of_answer - 1]; ++mdx)
                    {
                        array_check[idx + kdx][jdx + mdx] = 1;
                    }
                }

            }
        }
    }
    return;
}
//numberofanswer 만큼 반복문 돌려서 찾고 ㄱ,걸 다시 그만큼 반복하는 구조로 함, sorting check가 1이면 패스하게 짬, 내부에서 출력하게 하자,,
void sorting_print(int n)
{
    int idx, jdx;
    int min_val, min_index;
    for (idx = 0; idx < n; ++idx)
    {
        sorting_check[idx] = 0;
    }

    for (idx = 0; idx < n; ++idx)
    {
        min_val = 10000;
        min_index = -1;
        for (jdx = 0; jdx < n; ++jdx)
        {
            if (sorting_check[jdx] == 1)
                continue;
            if (mul_answer[jdx] < min_val)
            {
                min_val = mul_answer[jdx];
                min_index = jdx;
            }
            else if ((mul_answer[jdx] == min_val)&&(row_answer[jdx] < row_answer[min_index]))
            {
                min_val = mul_answer[jdx];
                min_index = jdx;
            }
        }
        printf("%d %d ", row_answer[min_index], col_answer[min_index]);
        sorting_check[min_index] = 1;
    }
    printf("\n");
    return;
}

int main(void)
{

    freopen("input.txt", "r", stdin);
    int T, N, test_case;

    scanf("%d", &T);
    int idx, jdx, kdx, mdx, ndx;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &N);
        for (idx = 0; idx < N; ++idx)
        {
            for (jdx = 0; jdx < N; ++jdx)
            {
                scanf("%d", &input_array[idx][jdx]);
                array_check[idx][jdx] = 0; // only n * n initialization
            }
        }
        number_of_answer = 0; //initial
        Finding_answer(N);

        //numberofanswer 만큼 반복문 돌려서 찾고 ㄱ,걸 다시 그만큼 반복하는 구조로 함, sorting check가 1이면 패스하게 짬, 내부에서 출력하게 하자,,
        printf("#%d %d ", test_case, number_of_answer); 
        sorting_print(number_of_answer);

       /* printf("%d\n", N);
        for (idx = 0; idx < number_of_answer; ++idx)
        {
                printf("%d ", mul_answer[idx]);
        }
        printf("\n");
        */

        /*printf("%d\n", N);
        for (idx = 0; idx < N; ++idx)
        {
            for (jdx = 0; jdx < N; ++jdx)
            {
                printf("%d ", input_array[idx][jdx]);
            }
            printf("\n");
        }*/

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

SW1259

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include<iostream>
#include<string.h>
#include<cmath>
#define MAX_VALUE 10000
using namespace std;

int row_answer[20];
int col_answer[20];
int sorting_check[20]; /// need, saved number of answer
int number_of_answer;

int find_first_idx(int n)
{
    int idx, jdx;
    int first_idx;
    int find_flag = 0;
    int check_flag = 0;

    for (idx = 0; idx < n; ++idx)
    {
        if (find_flag)
            continue;

        check_flag = 0;
        for (jdx = 0; jdx < n; ++jdx)
        {
            if (row_answer[idx] == col_answer[jdx])
                check_flag = 1;
        }
        if (check_flag != 1)
        {
            find_flag = 1;
            first_idx = idx;
            return idx;
        }
    }

}

void print_answer(int n, int first_idx)
{
    int idx, jdx;
    int current_col_idx = first_idx;
    printf("%d %d ", row_answer[first_idx], col_answer[first_idx]);

    for (idx = 0; idx < n - 1; ++idx)
    {
        current_col_idx;
        int flag = 0;
        for (jdx = 0; jdx < n; ++jdx)
        {
            if (flag)
                continue;
            if (col_answer[current_col_idx] == row_answer[jdx])
            {
                flag = 1;
                current_col_idx = jdx;
                printf("%d %d ", row_answer[jdx], col_answer[jdx]);
            }
        }

    }

}

int main(void)
{

    //freopen("input.txt", "r", stdin);
    int T, N, test_case;
    int first_idx;

    scanf("%d", &T);
    int idx, jdx, kdx, mdx, ndx;
    for (test_case = 1; test_case <= T; ++test_case)
    {
        scanf("%d", &N);
        for (idx = 0; idx < N; ++idx)
        {
            scanf("%d %d ", &row_answer[idx], &col_answer[idx]);
        }

        first_idx = find_first_idx(N);
        printf("#%d ", test_case);
        print_answer(N, first_idx);
        printf("\n");
        /* printf("%d\n", N);
         for (idx = 0; idx < number_of_answer; ++idx)
         {
                 printf("%d ", mul_answer[idx]);
         }
         printf("\n");
         */

        /* printf("%d\n", N);
         for (idx = 0; idx < N; ++idx)
         {
             printf("%d %d ", row_answer[idx], col_answer[idx]);
         }
         printf("\n");*/

    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}