글 읽기 - 20%대에서 틀렸다고 나옵니다. 반레 찾아주세요..

hsko0926 6년 전 0

테스트케이스 맞다고 나오는데 어디서 틀린지 모르겠습니다.

DP[i][j] := i를 만드는데 (j+1)번째까지 동전 써서 만들수있는 경우의 수 (누적)

예를 들어,

dp[10][1] = 1원 5원 써서 10원 만들 수 있는 경우의 수

dp[10][2] = 1원 5원 10원 써서 10원 만들 수 있는 경우의 수

입니다.

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

long long dp[10001][101];
vector <pair<int, int>> v;

int main()
{
	int T, K; scanf("%d %d", &T, &K);
	for (int i = 0; i < K; i++)
	{
		int temp1, temp2; scanf("%d %d", &temp1, &temp2);
		v.push_back({ temp1, temp2 });
	}
	sort(v.begin(), v.end());

	for (int i = 0;i<=v[0].second;i++)
	{
		dp[(v[0].first)*i][0] = 1;
	}
	//for(int i=0;i<=T;i++) printf("dp[%d][0]=%d\n", i, dp[i][0]);

	for (int j = 1; j < K; j++)
	{
		int until = v[j].first*v[j].second;
		for (int i = 0; i <= T; i++)
		{
			dp[i][j] = dp[i][j - 1];
			if (i <= until && i>=v[j].first)
			{
				dp[i][j] += dp[i - v[j].first][j];
			}
			else if (i > until)
			{
				dp[i][j] += dp[i - until][j-1];
			}
		//	printf("dp[%d][%d]=%d\n", i, j, dp[i][j]);
		}
	}
	printf("%lld\n", dp[T][K - 1]);	return 0;
}

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

문제

문제

출처

ICPC

20%대에서 틀렸다고 나옵니다. 반레 찾아주세요..

hsko0926 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말