“첫 번째와 두 번째 절반 비트의 합이 같은 짝수 길이 이진 시퀀스 계산”문제는 정수가 주어 졌다는 것을 나타냅니다. 이제 전반과 후반이 동일한 수의 세트 비트를 갖도록 2 * n 크기의 이진 시퀀스를 구성하는 방법의 수를 찾으십시오.
차례
예
2
6
설명
바이너리 시퀀스는 0000, 1001, 1010, 0110, 0101, 1111입니다. 따라서 총 개수는 1입니다.
접근
순진한 접근
문제를 해결하는 한 가지 방법은 재귀를 사용하는 것입니다. 따라서 우리는 양쪽 절반에 설정해야하는 비트 수를 추적 할 것입니다. 따라서 솔루션은 3 상태 솔루션입니다. 상태는 전반에 설정해야하는 비트 수, 후반에 설정할 남은 비트 수, 통과하는 비트 수입니다. 일반적인 재귀 솔루션은 아래 코드와 같습니다.
#include <bits/stdc++.h>
using namespace std;
int n;
int rec(int a, int b, int i){
if(i == n)
if(a == 0 && b == 0)
return 1;
else
return 0;
return rec(a-1, b-1, i+1) + rec(a-1, b, i+1) + rec(a, b-1, i+1) + rec(a, b, i+1);
}
int main(){
int t;cin>>t;
while(t--){
cin>>n;
int ans = 0;
for(int i=0;i<=n;i++)
ans += rec(i, i, 0);
cout<<ans;
}
}
해결책은 좋지만 매우 비효율적입니다. 따라서 시간 복잡성을 개선합니다. 우리는 사용할 수 있습니다 동적 프로그래밍. 그러나 여전히 시간 복잡도는 세 가지 상태로 인해 O (N ^ 3)입니다.
더 나은 접근 방식
더 나은 접근 방식은 재귀 공식을 변경하고 사용하는 것입니다. 동적 프로그래밍 문제를 해결합니다. 전반과 후반에 설정할 비트 수를 유지하는 대신. 차이를 사용하여 두 상태를 단일 상태로 줄일 수 있습니다. 이제 우리의 재귀 공식이 변경되어 시간 복잡성과 공간 복잡성이 변경되었습니다. O (N ^ 2) 시간에 실행될 수있는 솔루션을 작성할 수 있습니다.
전반 및 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int n;
int rec(int diff, int i, vector<vector<int>> &dp){
if(i == n)
if(diff == 0)
return 1;
else
return 0;
if(dp[diff+n][i] != -1)
return dp[diff+n][i];
return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}
int main(){
cin>>n;
vector<vector<int>> dp(2*n+2, vector<int>(n+1, -1));
int ans = rec(0, 0, dp);
cout<<ans;
}
6
924
전반 비트와 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 Java 코드
import java.util.*;
class Main{
static int n;
static int rec(int diff, int i, int dp[][]){
if(i == n)
if(diff == 0)
return 1;
else
return 0;
if(dp[diff+n][i] != -1)
return dp[diff+n][i];
return dp[diff+n][i] = rec(diff+1, i+1, dp) + rec(diff-1, i+1, dp) + 2*rec(diff, i+1, dp);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int dp[][] = new int[2*n+2][n+1];
for(int i=0;i<2*n+2;i++){
for(int j=0;j<n+1;j++)
dp[i][j] = -1;
}
int ans = rec(0, 0, dp);
System.out.print(ans);
}
}
6
924
복잡성 분석
시간 복잡성
O (N ^ 2), 문제에 N ^ 2 개의 다른 상태가 있었기 때문입니다. 따라서 시간 복잡도는 다항식입니다.
공간 복잡성
O (N ^ 2), 2D DP 어레이를 만들었 기 때문입니다. 따라서 공간 복잡성도 다항식입니다.
최선의 접근 방식
최선의 접근 방식은 이항 계수를 사용하여 문제에 대한 답을 계산하는 것입니다. 우리는 두 반쪽이 독립적이라고 생각할 수 있습니다. 그런 다음 그들이 독립적이고 우리는 단순히 약간의 비트를 설정해야합니다. n 비트 중 k 비트를 설정해야한다고 생각해보십시오. 그래서 우리는 nCk * nCk와 같은 방법의 수를 간단히 쓸 수 있습니다. 따라서 우리가 k에 대해 0과 같은 값을 계산하면 k는 n과 같습니다. 우리는 답을 찾았을 것입니다.
전반 및 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 C ++ 코드
#include <bits/stdc++.h>
using namespace std;
int main(){
int n;cin>>n;
int C = 1, answer = 1;
for (int i = 1; i<=n ; i++)
{
C = (C * (n+1-i))/i;
answer += (C*C);
}
cout<<answer;
}
6
924
전반 비트와 후반 비트의 합계가 동일한 짝수 길이 이진 시퀀스를 계산하는 Java 코드
import java.util.*;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int answer = 1, C = 1;
for(int i = 1; i<=n; i++)
{
C = (C * (n+1-i))/i;
answer += (C*C);
}
System.out.print(answer);
}
}
6
924
복잡성 분석
시간 복잡성
의 위에), N까지 단일 루프를 실행했기 때문입니다. 따라서 알고리즘은 선형 시간 복잡도를 갖습니다.
공간 복잡성
O (1), 공간 복잡성이 일정하기 때문입니다.
