[LeetCode] 2834. Find the Minimum Possible Sum of a Beautiful Array

문제 URL :  https://leetcode.com/problems/find-the-minimum-possible-sum-of-a-beautiful-array/

Find the Minimum Possible Sum of a Beautiful Array - LeetCode

 

문제 접근법 : 쉽게 얘기하면  수학문제입니다.

beautiful array를 찾으란 문제인데 target이 존재하지않다고 가정하면

중복되지않고 오름차순이면 모든 array는 beautiful 입니다.

그러나 target 존재 할때 array[i] + array[j] == target이 되지않도록 array를 구성하면서

길이가 n인 array[i]의 모든합이 최소가 되도록 구성하는 문제입니다.

 

 

 

간단하게 길이가 target이 10인  길이가 n을 찾아볼때 n일때 우선은 n의 길이가 크다고 가정해보죠

 

그렇다면 최소로 만들려면 반드시 1,2,3,4,5,6,7,8,9,10 ....으로 만들어야하지만

1+9 =10 ,2+8=10, 3+7=10 , 4+6=10 이되는 수가 여러개 존재합니다.

그렇다면 6부터 9까지는 지워야겠죠?

 

그러면 1,2,3,4,5, 10,11,12.... 이 되겠죠?

여기서 눈치채신분이 있을겁니다. 바로 target의 절반만큼 수열을 만들면

1,2,3,4,5 어떤 두수를 합치더라도 절대 10이 될수없다는것을

그리고 10부터 시작하면 어떤두수를 합치더라도 10이될수없다는것을 알게됐습니다.

 

마지막으로 남은건 길이가 n이 target/2보다 작을때는

굳이 target 이상의 수를 만들필요가없습니다. 그저 1부터 min(target/2, n) 개수만큼 수열을만들면 두쌍의 수의 합은 절대 target이 될수없을테니까요

 

n이 target/2보다 크거나 같을때는 길이가 10이라고 할때

1,2,3,4,5 를 전부 포함하고 10 ,11,12,13,14 가 되도록 만든후 그합을 구하면 됩니다.

 

1,2,3,4,5, 수학 공부를 조금 해보신분이라면 바로 어떤공식이 떠오를거라 생각하실지 감이 올겁니다.

바로 수열의 합 공식을이용해서 바로 풀수가있습니다.

 

소스코드 : 

class Solution {
public:
long long acc(long long t){
	return (t*(t+1))/2;
}
int minimumPossibleSum(int n, int target) {
	if(n==1) return 1;
	long long sum = 0;
	long long mod = 1e9+7;
	int t= target/2;
	if(n<t)return acc(n) % mod;
	sum+=acc(t)+acc(target+n-t-1) -acc(target-1);
	return sum%mod;
}

};

궁금한점 혹은 모르는점 어떤질문이든 댓글은 언제나 환영입니다.