글 읽기 - 1415 사탕 C++ 제발 도와주세요ㅠ

blou888 2년 전 0

값들을 입력을 받고, 카운팅 정렬을 통해서 벡터에 값과, 개수를 넣어주고

그리고 소수 판정 is_div를 통해서 소수인 idx는 true로 만들어주고

백트래킹을 하면서 사탕을 선택을 했을 경우랑, 선택하지 않았을 경우를 나눠서 깊이 우선탐색을 하고

모든 사탕을 선택하거나 선택하지 않았을 경우, 그 때의 값을 is_div를 통해서 소수라면 1을 리턴을 해 주고 아니면, 0을 리턴을 했습니다.. 혹시 어디에 논리적 오류가 있는지 알 수 있습니까?

value 배열에 저장을 하면서 리턴을 해 주고, 만약 value에 그 값이 있다면 그 숫자를 리턴을 해 줘서 탐색을 멈추고 돌아가도록 만들었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int arr[10001];
int N;
vector<pair<int, int>> v;
unsigned int value[51][500001];
bool is_div[500001];

unsigned int findCandy(int deep, int val) {
	if (deep >= v.size()) {
		if (is_div[val]) return 0;
		else return value[deep][val] = 1;
	}
	if (value[deep][val] != 0) {
		return value[deep][val];
	}
	//아무것도 넣지 않았을 때
	int sum = 0;
	value[deep][val] += findCandy(deep + 1, val);
	//사탕을 1개부터~N개까지 골라 잡았을 때
	for (int i = 0; i < v[deep].second; i++) {
		//first는 가격
		//second는 개수
		value[deep][val] += findCandy(deep + 1, val + (v[deep].first * (1 + i)));
	}
	return value[deep][val];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	for (int i = 0; i < N; i++) {
		int value;
		cin >> value;
		arr[value]++;
	}

	//오름 차순 정렬 + 사탕 개수까지 
	for (int i = 0; i <= 10000; i++) {
		if (arr[i] != 0) {
			v.push_back({ i,arr[i] });
		}
	}


	is_div[1] = true; is_div[0] = true;
	for (int i = 2; i < 250001; i++) {
		if (is_div[i]) continue;
		for (int j = 2; j * i <= 500000; j++) {
			is_div[i * j] = true;
		}
	}

	cout << findCandy(0, 0) << "\n";
	
}

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

문제

문제

출처

ICPC

1415 사탕 C++ 제발 도와주세요ㅠ

blou888 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말