득이공간
[백준 C++] 1208 부분수열의 합 2 - 중간에서만나기 본문
문제풀이
1182번(부분수열의 합) 문제에서 N의 크기만 다른 문제입니다.
N의 크기가 20일 때는 브루트포스 알고리즘을 이용해서 한 번에 풀 수 있지만($2^{20}$번 연산 수행),
이 문제에서는 N의 크기가 40이기 때문에 같은 방법으로 풀면 시간초과가 발생합니다. ($2^{40}$번 연산 수행)
따라서 전체 수열을 반으로 나눠서 왼쪽 부분 수열, 오른쪽 부분 수열의 합을 각각 구해주어 풀어야 합니다.
풀이 과정은 다음과 같습니다.
1. 브루트포스 알고리즘을 이용해서 왼쪽 수열의 모든 경우의 부분 수열의 합 계산
2. 해시 맵에 1번 단계에서 구한 각각의 합의 개수를 저장
3. 브루트포스 알고리즘을 이용해서 오른쪽 수열의 모든 경우의 부분 수열의 합(sum) 계산
4. 해시 맵에 저장된 [S - sum]의 개수 만큼 카운트
* 주의사항. S가 0일때, 왼쪽 수열에서 공집합을 선택한 경우와 오른쪽 수열에서 공집합을 선택한 경우가 카운팅되므로 마지막에 카운트 -1을 해주어야 합니다. (부분수열의 크기는 양수)
코드
#include <iostream>
#include <unordered_map>
using namespace std;
int N, S;
int Seq[40];
unordered_map<int, int> Left;
bool Select[40];
long long Cnt;
void LB(int Idx, int Size)
{
if (Idx == Size)
{
int Sum = 0;
for (int i = 0; i < Size; ++i)
{
if (Select[i])
{
Sum += Seq[i];
}
}
++Left[Sum];
return;
}
Select[Idx] = true;
LB(Idx + 1, Size);
Select[Idx] = false;
LB(Idx + 1, Size);
}
void RB(int Idx, int Size)
{
if (Idx == Size)
{
int Sum = 0;
for (int i = Size / 2; i < Size; ++i)
{
if (Select[i])
{
Sum += Seq[i];
}
}
Cnt += Left[S - Sum];
return;
}
Select[Idx] = true;
RB(Idx + 1, Size);
Select[Idx] = false;
RB(Idx + 1, Size);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> N >> S;
for (int i = 0; i < N; ++i)
{
cin >> Seq[i];
}
LB(0, N / 2);
RB(N / 2, N);
if (S != 0)
{
cout << Cnt;
}
else
{
cout << Cnt - 1;
}
}
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 2263 트리의 순회 - 트리 (0) | 2024.04.12 |
---|---|
[백준 C++] 1509 팰린드롬 분할 - 다이나믹프로그래밍 (0) | 2024.04.09 |
[백준 C++] 17387 선분 교차 2 - 많은조건분기 (0) | 2024.04.05 |
[백준 C++] 16946 벽 부수고 이동하기 4 - 너비우선탐색 (0) | 2024.03.26 |
[백준 C++] 10775 공항 - 분리집합 (0) | 2024.03.25 |