[BOJ-1940] 주몽

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

1940번: 주몽

 

 

음... dfs를 이용해 조합으로 풀었다.

 

히든 케이스가 상당히 빈약한듯 하다

 

다른 방법이 정해일 것 같은데 한 번에 통과해서 놀랐다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int n, m, res;
vector<int> vec, sel;

void dfs(int n) {
	if (sel.size() == 2) {
		if (sel[0] + sel[1] == m) {
			res += 1;
		}
		return;
	}

	for (int i = n; i < vec.size(); i++) {
		sel.push_back(vec[i]);
		dfs(i + 1);
		sel.pop_back();
	}
}


int main(void) {

	scanf("%d", &n);
	scanf("%d", &m);

	for (int i = 0, temp; i < n; i++) {
		scanf("%d", temp);
		vec.push_back(temp);
	}

	dfs(0);

	printf("%d\n", res);

	getchar();
	getchar();

	return 0;
}