작은 성냥개비 소녀가 있다고 가정해 봅시다. 그리고 우리는 성냥개비 소녀가 가지고 있는 성냥개비를 정확히 알고 있습니다. 우리는 성냥개비를 모두 사용하여 정사각형 하나를 만들 수 있는 방법을 찾아야 합니다. 막대기를 부러뜨리면 안되지만 연결할 수 있으며 각 성냥개비는 정확히 한 번만 사용해야 합니다. 우리의 입력은 소녀가 가지고 있는 여러 성냥개비로, 막대기 길이로 표시됩니다. 우리의 출력은 성냥개비 소녀가 가지고 있는 모든 성냥개비를 사용하여 하나의 정사각형을 만들 수 있는지 여부를 나타내기 위해 true 또는 false가 될 것입니다. 따라서 입력이 [1,1,2,2,2]와 같으면 답은 참이 됩니다. 길이가 2인 정사각형을 만들 수 있으므로 한 변에는 길이가 1인 막대가 두 개 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- solve()라는 재귀 메서드를 정의합니다. 이것은 인덱스, 합계 배열, 대상 및 숫자 배열을 사용합니다. 따라서 이것은 다음과 같이 작동합니다 -
- 인덱스>=숫자 크기인 경우
- sum[0], sum[1], sum[2]가 모두 targer와 같으면 true를 반환합니다.
- 0에서 3 사이의 i에 대해 -
- sums[i] + nums[index]> target이면 루프의 다음 부분을 건너뜁니다.
- 합[i] :=합[i] + 숫자[색인]
- solve(index + 1, sums, target, nums)가 true이면 true를 반환합니다.
- 합[i] :=합[i] – 숫자[색인]
- 거짓 반환
- 메인 방법에서 다음을 수행하십시오. -
- nums에 요소가 없으면 false를 반환합니다.
- x :=0
- 0에서 숫자 크기까지 범위에 있는 i의 경우 x를 숫자만큼 증가[j]
- x가 4로 나누어 떨어지면 false를 반환합니다.
- nums 배열 정렬
- 크기 4의 배열 합계 만들기
- 해결(0, 합계, x/4, 숫자) 반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(int idx, vector <int>& sums, int target, vector <int>& nums){
if(idx >= nums.size()){
return sums[0] == sums[1] && sums[1] == sums[2] && sums[2] == target;
}
for(int i = 0; i < 4; i++){
if(sums[i] + nums[idx] > target)continue;
sums[i] += nums[idx];
if(solve(idx + 1, sums, target, nums)) return true;
sums[i] -= nums[idx];
}
return false;
}
bool makesquare(vector<int>& nums) {
if(nums.size() == 0) return false;
int x = 0;
for(int i = 0; i < nums.size(); i++){
x += nums[i];
}
if(x % 4) return false;
sort(nums.rbegin(), nums.rend());
vector <int> sum(4);
return solve(0, sum,x / 4, nums);
}
};
main(){
vector<int> v = {1,1,2,2,2};
Solution ob;
cout << (ob.makesquare(v));
} 입력
[1,1,2,2,2]
출력
1