글 읽기 - 1415 사탕 질문이요

znxkznxk1030 6년 전 0

이렇게 풀었는데 아무리 생각해봐도 어떤 부분에서 틀렸는지 알기 힘드네요..

어떤점이 틀렸나요??

#include <iostream>
#include <cmath>

#define MAX_NUM 500001
#define PRIME false
#define NOT_PRIME true
#define ll long long int

using namespace std;

void prime_checking();
void input();
void process();
int ans();

int N;
bool is_prime[MAX_NUM];
int candy[MAX_NUM];
int dp[51][MAX_NUM];
int level = 1;

int main(){
	prime_checking();
	input();
	process();
	cout<<ans();
	return 0;
}

int ans(){
	int answer = 0;
	for(int i = 2; i < MAX_NUM; i++)
		if(is_prime[i] == PRIME)
			answer += dp[level - 1][i];
	return answer;
}

void process(){
	int s = 0;
	dp[0][0] = 1 + candy[0];
	
	for(int i = 0; i <= 10001; i++)
	{
		if(candy[i] == 0) continue;
		
		for(int j = 0; j <= candy[i]; j++)
		{
			for(int k = 0; k <= s; k++)
			{
				dp[level][k + j*i] += dp[level - 1][k];
			}
		}
		level++;
		s += i * candy[i];
	}
}

void input(){
	cin>> N;
	for(int i = 0; i < N; i++)
	{
		int t; cin>>t;
		candy[t]++;
	}
}

void prime_checking(){
	int limit = sqrt(MAX_NUM);
	is_prime[1] = NOT_PRIME;
	
	for(int i = 2; i < limit; i++)
	{
		if(is_prime[i] == PRIME)
			for(int j = i * i; j <= MAX_NUM - 1; j += i)
				is_prime[j] = NOT_PRIME;
	}
}

portableangel 6년 전 0

이 문제 조건엔 안 써있지만 결과가 int를 넘어갑니다

long long은 안 넘어가네요

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

문제

문제

출처

ICPC

1415 사탕 질문이요

znxkznxk1030 6년 전 0

portableangel 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말