• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

트리의 특성을 활용해서 이런 방식으로 풀이를 해보았습니다.

22.06.07 23:28 작성 조회수 129

0

 
#include <iostream>
#include <vector>
using namespace std;
int n = 0, ch[11], l[11];
vector<int> v;
void DFS(int L) {
	if (L == n + 1) {
		int sum = 0;
		for (int i = 1; i <= n; i++) {
			if (ch[i] == 1) {
				sum += l[i];
			}
		}
		v.push_back(sum);
	}
	else {
		ch[L] = 1;
		DFS(L + 1);
		ch[L] = 0;
		DFS(L + 1);
	}
}

int main() {
	//FILE* fp = nullptr;
	//freopen_s(&fp, "input.txt", "rt", stdin);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l[i];
	}
	v.push_back(0);
	DFS(1);
	int s = v.size();
	for (int i = 1; i <= s/2; i++) {
		int l = v[i];
		int r = v[s - i];
		if (l == r) {
			cout << "YES";
			return 0;
		}
	}
	cout << "NO";
	return 0;
}

트리의 정가운데를 기준으로 나눠서 생각해보면 

반대편에 있는 값이 서로 겹치지 않는 값이더라구요.

위 특성을 활용하면 이런 풀이도 가능한 것 같습니다.

 

 

답변 0

답변을 작성해보세요.

답변을 기다리고 있는 질문이에요.
첫번째 답변을 남겨보세요!