글 읽기 - 소스 한번 봐주세요!!

jwsong 7년 전 0

dp를 사용해서 구현했는데 계속 오버플로우가 나서그런가 틀렸다고 나오네요...

혹시 제가 놓친부분이 있거나 오버플로우 방지하는 방법이 알고싶어요!

#include <stdio.h>
int num[100];
unsigned long long dp[21];
unsigned long long temp[21];

int main(void) {
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++){
		scanf("%d", &num[i]);
	}
	dp[num[0]]=1;
	
	for(int i=1; i<n-1; i++){
		for(int j=0; j<=20; j++){
			temp[j] = dp[j];
			dp[j]=0;
		}
		for(int j=0; j<=20; j++){
			if(j+num[i]<=20){
				dp[j+num[i]] += temp[j];
			}
			if(j-num[i]>=0){
				dp[j-num[i]] += temp[j];
			}
		}
		for(int j=0; j<=20; j++) printf("%d ",dp[j]);
		printf("\n");
	}
	printf("%d", dp[num[n-1]]);
	return 0;
}

hsnks100 7년 전 0

dp 의 정의가 어떻게 되는진 모르겠는데 1차원으론 풀기가 좀 어려울 듯 싶습니다.

index 까지 왔을 때 어떤수를 만드는 경우의 수 이런식으로 dp 를 짜셔야 할 듯 합니다.

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

문제

문제

출처

ICPC

소스 한번 봐주세요!!

jwsong 7년 전 0

hsnks100 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말