백준 13751(Barbells)

www.acmicpc.net/problem/13751

13751번: Barbells

알고리즘 처음 시작할때 풀었었는데 계속 시간초과 났던 문제.

지금 보니 너무 쉬운데 그때는 그게 그렇게 안 보였다. 

 

근데 사실은 방금 전까지도 답이 안나와서 왜 그럴까 한참을 생각하긴 했음

 

단순하게 왼쪽에 넣고 오른쪽에 넣고 안 넣고 이렇게 세가지 경우를 최대 14가지에 대해서 모두 조사해주면 된다.

 

이럴 경우에 3^14 1억이 안되므로 시간에 걸리지 않는다.

 

중복을 처리하기 위해서 set 자료구조를 사용하였다.

 

아 그런데 그 내가 solve함수에서 if(index==p)return 을 맨위에 나뒀더니 원하는 정답이 나오지 않았었는데 

잘 생각해보면 당연하다. 주의하자

#include<iostream>
#include<set>
using namespace std;

int b, p;
int plate[14];
int bar[14];
int sum;
int num;
set<int> s;
set<int> ans;

void solve(int index, int l, int r) {
	if (l > sum / 2 || r > sum / 2) {
		return;
	}
	if (l == r) {
		s.insert(l * 2);
	}
	if (index == p) return;
	solve(index + 1, l + plate[index], r);
	solve(index + 1, l, r);
	solve(index + 1, l, r + plate[index]);
}

int main() {
	cin >> b >> p;
	for (int i = 0; i < b; i++) {
		cin >> bar[i];
	}
	for (int i = 0; i < p; i++) {
		cin >> plate[i];
		sum += plate[i];
	}
	solve(0, 0, 0);
	for (int i = 0; i < b; i++) {
		for (auto it = s.begin(); it != s.end(); it++) {
			ans.insert(bar[i] + *it);
		}
	}
	for (auto it = ans.begin(); it != ans.end(); it++) {
		cout << *it << "\n";
	}
}