-
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