글 읽기 - 문제 질문 있습니다.

dksdmssh1212 4년 전 0

왜 1000이 안되는지 궁금합니다..

재귀를 연습하고 싶어서 재귀로 해봤는데 잘 안되네요...

알려주시면 감사하겠습니다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int T, K=1001;
int flag = 0;
int tripleCount = 0;
vector<int> set;

void calculate_triple(vector<int>& triples) {
	triples.push_back(1);
	int temp = 0;
	for (int i = 1; i < 46; i++) {
		temp = triples[i - 1];
		triples.push_back(temp + (i + 1));
	}
}

void powerSet(vector<int>& set, int input) {
	int sum = 0;
	for (int i = 0; i < set.size(); i++) {
		sum = set[i];
		if (sum == input) {
			flag++;
			break;
		}
		else if (sum > input) {
			break;
		}
	}
}

void calculateSet(vector<int>& triples, vector<bool>& visit, int depth, int tCount) {
	if (depth == 46 || tCount == 3) {
		int sum = 0;
		for (int i = 0; i < visit.size(); i++) {
			if (visit[i] == true) {
				sum += triples[i];
			}
		}
		set.push_back(sum);
		return;
	}
	visit[depth] = true;
	calculateSet(triples, visit, depth + 1, tCount + 1);
	visit[depth] = false;
	calculateSet(triples, visit, depth + 1, tCount);
}



int main() {
	vector<int> inputs;
	vector<int> triples;
	vector<bool> visit(46);
	
	calculate_triple(triples);
	int T;
	cin >> T;

	calculateSet(triples, visit, 0, 0);
	int input;
	for (int i = 0; i < T; i++) {
		cin >> input;
		powerSet(set, input);
		if (flag > 0) {
			cout << 1 << '\n';
		}
		else {
			cout << 0 << '\n';
		}
		flag = 0;
	}
	
	return 0;
}

minjoonist 4년 전 0

어떤 로직으로 푸신건지는 잘 모르겠지만 DP로 푸셔야 합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

문제 질문 있습니다.

dksdmssh1212 4년 전 0

minjoonist 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말