백준 1182 c++ "부분수열의 " -PlusUltraCode-

https://www.acmicpc.net/problem/1182

 

[필자 사고]

처음 문제를 보고 N의 크기를 봤더니 20이였다.

시간적 여유가 있고 가능한 알고리즘을 생각해본 결과 브루투포스가 떠올랐다.

그 중에서도 정해진 배열의 idx에서 특정 원소들만 빼고 더한다는 사고를 할 수 있는 알고리즘은

DFS 를 이용한 빽트래킹 알고리즘이였따. 

어떠한 사고과저으로 해당 알고리즘을 떠올랐는지가 중요한 문제같ㄷ.

 

아래는 자세한 코드해설이다.

[코드 해설]

Input() 함수

• 표준 입력을 통해 N (수열의 길이)과 S (목표 합)을 입력받습니다.
• 이후 N개의 정수를 벡터 arr에 저장합니다.

---

DFS(int idx, int sum) 함수

• 이 함수는 깊이 우선 탐색(DFS) 방식으로 부분수열을 탐색합니다.
• idx는 현재 탐색 중인 수열의 인덱스입니다.
• sum은 현재까지 선택한 부분수열의 합입니다.

주요 로직:

• 종료 조건: idx >= N이면 재귀 종료 (배열 끝까지 탐색한 경우).
• 현재 인덱스의 값을 포함했을 때, sum + arr[idx] == S라면 조건을 만족하므로 결과 카운트 증가.
• 두 갈래로 재귀 호출:
  1. 현재 인덱스의 값을 선택하지 않고 다음 인덱스로 이동 (DFS(idx + 1, sum))
  2. 현재 인덱스의 값을 선택하고 다음 인덱스로 이동 (DFS(idx + 1, sum + arr[idx]))

이렇게 하면 모든 가능한 부분수열을 탐색하게 됩니다.

---

Game_Start() 함수

• 탐색을 시작하는 함수입니다.
• DFS(0, 0)으로 0번째 인덱스에서 부분수열의 합 0으로 시작합니다.
• 모든 탐색이 끝난 후 resultCount를 출력합니다.

[소스 코드]

#include <iostream>
#include <vector>

using namespace std;

int N, S;
vector<int> arr;
int resultCount = 0;

void Input() {
	cin >> N >> S;
	for (int i = 0; i < N; i++) {
		int num;
		cin >> num;
		arr.push_back(num);
	}
}

void DFS(int idx, int sum) {

	if (idx >= N)return;

	if (sum + arr[idx] == S)resultCount++;

	DFS(idx + 1, sum);
	DFS(idx + 1, sum + arr[idx]);
}

void Game_Start() {
	DFS(0, 0);
	cout << resultCount;
}

int main(void) {
	Input();
	Game_Start();
}