ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • JUNGOL...109
    일지 2021. 8. 5. 13:37

    Intermediate_Coder/분할정복/숫자구슬(easy)


    문제                                            

    N개의 숫자 구슬이 <그림 1>과 같이 막대에 꿰어져 일자로 놓여 있다. 

    이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다.

     

    JUNGOL 분할정복 숫자구슬(easy) - 1

     

    이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다.

    예를 들어 세 그룹으로 나눈다고 할 때 <그림 2>와 같이 그룹을 나누면 

    그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고, 

    <그림 3>과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다. 

    숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다.

     

    JUNGOL 분할정복 숫자구슬(easy) - 2

     

    각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때,

    그 최대값을 출력하는 프로그램을 작성하시오. 

     

    입력 형식                                     

    첫째 줄에 구슬의 개수 N과 그룹의 수 M이 주어진다.

    둘째 줄에는 각 구슬이 적혀진 숫자가 왼쪽부터 차례로 주어진다. 

    N은 300 이하의 자연수, M은 N이하의 자연수이며, 구슬에 적혀진 숫자는 100 이하의 자연수이다. 

     

    출력 형식                                     

    각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때 그 최대값을 첫째 줄에 출력한다.

     

    *** M개의 각 그룹에 적어도 하나의 구슬이 포함되어야 함에 유의한다. *** 

     

    입력 예                                        

    8 3

    5 4 2 6 9 3 8 7

     

    출력 예                                        

    17


    NumberBeadEasy.h

    #define _CRT_SECURE_NO_WARNINGS
    
    #include <cstdio>
    #include <climits>
    
    class NumberBeadEasy : public Base
    {
    private:
    	int FindMinTotal(int arr[], int n, int totalArr[], int m, 
    		int prev = 0, int depth = 0);
    }

     

    NumberBeadEasy.cpp

    void NumberBeadEasy::Code()
    {
    	int n, m;
    
    	(void)scanf("%d %d", &n, &m);
    
    	int* arr = new int[n];
    	int* totalArr = new int[m];
    
    	for (int i = 0; i < n; i++)
    	{
    		(void)scanf("%d", &arr[i]);
    	}
    
    	printf("%d", FindMinTotal(arr, n, totalArr, m));
    
    	delete[] arr;
    	delete[] totalArr;
    }
    
    int NumberBeadEasy::FindMinTotal(int arr[], int n, int totalArr[], int m, 
    	int prev, int depth)
    {
    	if (depth == m - 1)
    	{
    		totalArr[depth] = 0;
    		for (int j = prev; j < n; j++)
    		{
    			totalArr[depth] += arr[j];
    		}
    
    		int maxTotal{ totalArr[0] };
    		for (int i = 1; i < m; i++)
    		{
    			if (maxTotal < totalArr[i])
    			{
    				maxTotal = totalArr[i];
    			}
    		}
    		return maxTotal;
    	}
    	
    	int minTotal{ INT_MAX };
    	for (int i = prev; i <= n - m + depth; i++)
    	{
    		totalArr[depth] = 0;
    		for (int j = prev; j <= i; j++)
    		{
    			totalArr[depth] += arr[j];
    		}
    		
    		int curTotal{ FindMinTotal(arr, n, totalArr, m, i + 1, depth + 1) };
    		if (curTotal < minTotal)
    		{
    			minTotal = curTotal;
    		}
    	}
    
    	return minTotal;
    }

     


    실행 결과 Time Limit Exceed(30)

    원인 C 스타일의 입출력으로 까지 변경했으나 유의미한 개선은 없었다. 검사하는 케이스 자체를 줄일 필요가 있어 보인다.

    처리 방법 고민 필요


     

    NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

     

    NadanKim/CodingTest_JUNGOL

    JUNGOL 코딩 테스트를 위한 저장소. Contribute to NadanKim/CodingTest_JUNGOL development by creating an account on GitHub.

    github.com

     

    댓글

Designed by Tistory.